xbuild.c

xtree程序实现

  function : int minOverlapSplitAxis(node_type **overnode)
  purpose  : to return the best split axis according to the minimum overlap
  parameter: node_type **overnode - the array of the over nodes overnode
  return   : int - the index of the best split axix according to the minimum overlap
*/
// **** Ray added
// Min overlap split
int minOverlapSplitAxis(node_type **overnode)
{
  int axis_chosen, *sorted_index;
  node_type *group1, *group2;
  // *** Ray changed
  //double new_margin_value, min_margin_value;
  double new_overlap_value, min_overlap_value;


  int i, j, k, l, stop, cut;
  // *** Ray added
  node_type *parentNode;
  int noOfOver;

  // *** Ray added
  parentNode = overnode[0]->parent;
  noOfOver = parentNode->snodeSize*M+1;


  // *** Ray changed
  //sorted_index = (int *)malloc(sizeof(int) * (M+1));
  sorted_index = (int *)malloc(sizeof(int) * noOfOver);
  tree_node_allocate(&group1);
  tree_node_allocate(&group2);


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

	sort_entries(sorted_index, overnode, i, noOfOver);   // sort the entries by axis i


	// *** Ray changed
	//new_margin_value = 0.0;
	new_overlap_value = 0.0;
	// *** Ray changed
	//stop = M - 2*m + 1;
	stop = M*parentNode->snodeSize - 2*m + 1;
	for (k=0; k<stop; k++) {

        	for (l=0; l<dim; l++) {
                	group1->a[l] = overnode[sorted_index[0]]->a[l];
	                group1->b[l] = overnode[sorted_index[0]]->b[l];
					// *** Ray changed
        	        //group2->a[l] = overnode[sorted_index[M]]->a[l];
                	//group2->b[l] = overnode[sorted_index[M]]->b[l];
					group2->a[l] = overnode[sorted_index[M*parentNode->snodeSize]]->a[l];
                	group2->b[l] = overnode[sorted_index[M*parentNode->snodeSize]]->b[l];
        	}        


		j = 0;
		cut = m + k;
		// *** Ray changed
		//while (j < M+1) {
		while (j < M*parentNode->snodeSize+1) {

			if (j < cut) {

				cal_MBR_node_node(group1->a, group1->b, group1, overnode[sorted_index[j]]);

			}
			else {

				cal_MBR_node_node(group2->a, group2->b, group2, overnode[sorted_index[j]]);

			}

			j++;

		}

		// *** Ray modified
		//for (l=0; l<dim; l++) {
		//
		//	new_margin_value = new_margin_value + group1->b[l] - group1->a[l];
		//	new_margin_value = new_margin_value + group2->b[l] - group2->a[l];
		//
		//}
		new_overlap_value = cal_overlap(group1, group2);
	}

	if (i == 0) {

                axis_chosen = i;
				// *** Ray modified
                //min_margin_value = new_margin_value;
				min_overlap_value = new_overlap_value;
	}
	else {

		// *** Ray modified
		//if (new_margin_value < min_margin_value) {
		if (new_overlap_value < min_overlap_value) {

			axis_chosen = i;
			// *** Ray modified
			//min_margin_value = new_margin_value;
			min_overlap_value = new_overlap_value;
		}

	}	
  }

  tree_node_deallocate(group1);
  tree_node_deallocate(group2);
  free(sorted_index);

  return(axis_chosen);

} /* minOverlapSplitAxis */



/*
  function : void minOverlapSplitIndex(node_type **overnode, int axis_chosen, node_type 
             *group1_chosen, node_type *group2_chosen)
  purpose  : to choose the best split index of the axis chosen axis_chosen according to
             minimum overlap
  parameter: node_type **overnode     - the array of the overflow nodes
             int axis_chosen          - the index of the axis chosen
	     node_type *group1_chosen - the first group to be split
	     node_type *group2_chosen - the second group to be split
  return   : none
*/
// *** Ray added
// min overlap split
void minOverlapSplitIndex(node_type **overnode, int axis_chosen, node_type 
*group1_chosen, node_type *group2_chosen)
{
  int split_index, *sorted_index;
  node_type *group1, *group2;  
  double new_overlap_value, min_overlap_value;
  double vol_at_index, new_vol;

  int i, j, k, stop, cut;
  
//FILE *fp;
  // *** Ray added
  node_type *parentNode;
  int noOfOver;

  // *** Ray added (to be changed)
  parentNode = overnode[0]->parent;
  noOfOver = parentNode->snodeSize*M+1;

  // **** Ray has changed
  //sorted_index = (int *)malloc(sizeof(int) * (M+1));
  sorted_index = (int *)malloc(sizeof(int) * noOfOver);

  // *** Ray changed
  tree_temp_node_allocate(&group1, parentNode->snodeSize);
  tree_temp_node_allocate(&group2, parentNode->snodeSize);

  
  sort_entries(sorted_index, overnode, axis_chosen, noOfOver);   // sort the entries by the axis, axis_chosen


  new_overlap_value = 0.0;  
  // *** Ray has changed
  //stop = M - 2*m + 1;
  stop = M*parentNode->snodeSize - 2*m + 1;
  for (k=1; k<stop; k++) {

	for (i=0; i<dim; i++) {
		group1->a[i] = overnode[sorted_index[0]]->a[i];
		group1->b[i] = overnode[sorted_index[0]]->b[i];
		// *** Ray changed
		//group2->a[i] = overnode[sorted_index[M]]->a[i];
		//group2->b[i] = overnode[sorted_index[M]]->b[i];
		group2->a[i] = overnode[sorted_index[M*parentNode->snodeSize]]->a[i];
		group2->b[i] = overnode[sorted_index[M*parentNode->snodeSize]]->b[i];
	}


	// *** Ray changed
	//cut = m + k; 
	cut = k; 
	//for (j=0; j<M+1; j++) {
	for (j=0; j<M*parentNode->snodeSize+1; j++) {
  
		if (j < cut) {
  
			cal_MBR_node_node(group1->a, group1->b, group1, overnode[sorted_index[j]]);
                        
		}
		else {
                        	
			cal_MBR_node_node(group2->a, group2->b, group2, overnode[sorted_index[j]]);
  
		}

	}

	new_overlap_value = cal_overlap(group1, group2);
 
        
	if (k == 1) {   

		split_index = k;
		min_overlap_value = new_overlap_value;
		vol_at_index = cal_vol(group1->a, group1->b) + cal_vol(group2->a, group2->b);

  	}
	else {   
                
		if (new_overlap_value < min_overlap_value) {

			split_index = k;
			min_overlap_value = new_overlap_value;
			vol_at_index = cal_vol(group1->a, group1->b) + cal_vol(group2->a, group2->b);

		}
		else {

			// *** Ray modified
			//new_vol = cal_vol(group1->a, group1->b) + cal_vol(group2->a, group2->b);
			//if (new_vol < vol_at_index) {
				split_index = k;
			//}

		}
  	}

  }

	
  for (i=0; i<dim; i++) {
	group1_chosen->a[i] = overnode[sorted_index[0]]->a[i];
	group1_chosen->b[i] = overnode[sorted_index[0]]->b[i];
	// *** Ray changed
	//group2_chosen->a[i] = overnode[sorted_index[M]]->a[i];
	//group2_chosen->b[i] = overnode[sorted_index[M]]->b[i];
	group2_chosen->a[i] = overnode[sorted_index[M*parentNode->snodeSize]]->a[i];
	group2_chosen->b[i] = overnode[sorted_index[M*parentNode->snodeSize]]->b[i];
  }

  // *** Ray changed
  //cut = m + split_index;
  cut = split_index;

  // *** Ray changed
  //for (j=0; j<M+1; j++) {
  for (j=0; j<M*parentNode->snodeSize+1; j++) {


	if (j < cut) {
                
		group1_chosen->ptr[j] = overnode[sorted_index[j]];

		overnode[sorted_index[j]]->parent = group1_chosen;
		cal_MBR_node_node(group1_chosen->a, group1_chosen->b, group1_chosen, overnode[sorted_index[j]]);
	}


	else {

		group2_chosen->ptr[j-cut] = overnode[sorted_index[j]];
                overnode[sorted_index[j]]->parent = group2_chosen;
                cal_MBR_node_node(group2_chosen->a, group2_chosen->b, group2_chosen, overnode[sorted_index[j]]);
	}

  }       


  // *** Ray changed
  //group1_chosen->vacancy = M - cut;
  //group2_chosen->vacancy = cut - 1;	// M - (M+1 - cut);
  if (cut%M == 0)
  {
	group1_chosen->vacancy = 0;
	group2_chosen->vacancy = M-1;

	group1_chosen->snodeSize = cut/M;
	group2_chosen->snodeSize = parentNode->snodeSize + 1 - group1_chosen->snodeSize;
  }
  else
  {
	group1_chosen->vacancy = M - cut%M;
	group2_chosen->vacancy = cut%M - 1;	// M - (M+1 - cut);

  // *** Ray added
	group1_chosen->snodeSize = cut/M + 1;
	group2_chosen->snodeSize = parentNode->snodeSize + 1 - group1_chosen->snodeSize;
  }

  tree_node_deallocate(group1);
  tree_node_deallocate(group2);
  free(sorted_index);

                       
  return;
        
} /* minOverlapSplitIndex() */



/*
  function : int split(node_type *splitting_node, node_type *extra_node, node_type *node1, node_type *node2) 
  purpose  : to split the node splitting_node and the extra_node into two nodes (node1 and node2)
  parameter: node_type *splitting_node - the splitting node
             node_type *extra_node     - the extra node to be inserted
	     node_type *node1          - the 1st splitted node
	     node_type *node2          - the 2nd splitted node
  return   : int - TRUE or FALSe : to indicate that this split is good or not
*/
// *** Ray changed
int split(node_type *splitting_node, node_type *extra_node, node_type *node1, node_type *node2) 
//void split(node_type *splitting_node, node_type *extra_node, node_type *node1, node_type *node2) 
{
  node_type **overnode;
  int axis_chosen;

  int i;

  // *** Ray added
  node_type *parentNode;
  int noOfOver;

  // *** Ray added 
  parentNode = splitting_node;
  noOfOver = parentNode->snodeSize*M+1;

  // **** Ray changed
  //overnode = (node_type **)malloc((M+1) * sizeof(node_type *));
  overnode = (node_type **)malloc(noOfOver * sizeof(node_type *));
  // *** Ray changed
  //for (i=0; i<M; i++) {
  for (i=0; i<noOfOver-1; i++) {
        overnode[i] = splitting_node->ptr[i];
if (overnode[i] == NULL) printf(" ^^^^^^^^^^^^^ overnode %d is NULL\n", i);
  }
if (overnode[0] == NULL) printf(" ^^^^^^^^^^^^^@overnode 0 is NULL\n");
  // *** Ray changed
  //overnode[M] = extra_node;
  overnode[noOfOver-1] = extra_node;

if (overnode[0] == NULL)
{
	printf("  !!!!!! sad0\n");
}

  // *** Ray changed
  //for(i=0; i < M; i++) {
  for(i=0; i < noOfOver-1; i++) {
        node1->ptr[i]=NULL;
        node2->ptr[i]=NULL;
  }

  // Topological split (in R*-tree)
if (overnode[0] == NULL)
{
	printf("  !!!!!! sad4\n");
}
  axis_chosen = ChooseSplitAxis(overnode);

  ChooseSplitIndex(overnode, axis_chosen, node1, node2);

  node1->attribute = NODE;
  node1->parent = splitting_node->parent;
  node1->id = NO_ID;

  node2->attribute = NODE;
  node2->parent = splitting_node->parent;
  node2->id = NO_ID;

  

  // *** Ray added
//printf("overlap : %f\n", (float)cal_overlap(node1, node2));
//if (cal_overlap(node1, node2) > MAX_OVERLAP)
//{
//	printf("larger overlap\n");
//}


  if (cal_overlap(node1, node2) > MAX_OVERLAP)
  {
//#ifdef RAYMOND
	  // *** Min-overlap split

	  // *** IMPORTANT
	  overnode[0]->parent = parentNode;

	  axis_chosen = minOverlapSplitAxis(overnode);
	  
	  minOverlapSplitIndex(overnode, axis_chosen, node1, node2);
	  
	  node1->attribute = NODE;
	  node1->parent = splitting_node->parent;
	  node1->id = NO_ID;
	  
	  node2->attribute = NODE;
	  node2->parent = splitting_node->parent;
	  node2->id = NO_ID;
	  
	  //free(overnode);
	  //if ((M*parentNode->snodeSize - node1->vacancy < MIN_FANOUT) || (M*parentNode->snodeSize - node2->vacancy < MIN_FANOUT))
	if ((node1->vacancy < 0) || (node1->vacancy > M) || (node2->vacancy < 0) || (node1->vacancy > M))
	{
		printf("@@@@@@@@@@@@@@@@@@ Vancancy is incorrect!\n");
	}
	  if ((M - node1->vacancy < MIN_FANOUT) || (M - node2->vacancy < MIN_FANOUT))
	  {
//printf("*******\n");

		  return FALSE;

	  }
//#endif
  }



  free(overnode);

  // *** Ray changed
  //return;
  return TRUE;

} /* split() */




/*
  function : void adjust_tree(node_type *splitting_node, int over_level, int old_level, node_type 
             *node1, node_type *node2, node_type *root)
  purpose  : to adjust the MBR of the trees from the splitting node at the node level over_level
             from two splitted nodes (node1 and node2) up to the root
  parameter: node_type *splitting_node - the splitting node
             int over_level            - the overnode level
	     int old_level             - the last level of the overnode level
	     node_type *node1          - the first splitted node
	     node_type *node2          - the second splitted node
	     node_type *root           - the root node
  return   : none
*/
// *** Ray has added the void return type of the function
void adjust_tree(node_type *splitting_node, int over_level, int old_level, node_type 
*node1, node_type *node2, node_type *root) 
{
  int split_child_no = 0;
  node_type *split_parent;

  int i, j;

  if(splitting_node->attribute == ROOT) { 

	/* The splitting node is the root */

	node1->parent = root;
	node2->parent = root;
	root->ptr[0] = node1;
	root->ptr[1] = node2;
if (node1 == NULL) printf("  ~~~~~~~~~ adjust_tree1\n");
if (node2 == NULL) printf("  ~~~~~~~~~ adjust_tree2\n");
	for (j=2; j<M; j++) 
		root->ptr[j] = NULL;
	root->parent = NULL;
	root->vacancy=M-2;
	root->attribute=ROOT;

	// *** Ray added
	root->snodeSize = 1;

	cal_MBR_node_node(root->a, root->b, node1, node2);

	extra_level++;
  }
  else { 

	/* The splitted is an intermediate node */

	split_parent = splitting_node->parent;

	// **** Ray changed
		//for(i=0; i < M; i++) {
        for(i=0; i < M*split_parent->snodeSize; i++) {
		if(split_parent->ptr[i] == splitting_node) { 
			split_child_no = i;
	             	break;
		}
        }
// **** cwwong
//	tree_node_deallocate(splitting_node);	

	/* insert first node */
	split_parent->ptr[split_child_no] = node1;
	node1->parent = split_parent;

	adjust_MBR_delete(node1);

	/* insert second node */
	
	if(split_parent->vacancy != 0) { 

		/* no need to split again */
		// **** Ray changed
           	//split_parent->ptr[M - split_parent->vacancy] = node2;
			split_parent->ptr[M*split_parent->snodeSize - split_parent->vacancy] = node2;

		node2->parent = split_parent;
		split_parent->vacancy--;

	//	cal_MBR_node_node(split_parent->a, split_parent->b, node1, split_parent);
		cal_MBR_node_node(split_parent->a, split_parent->b, node2, split_parent);

		adjust_MBR(split_parent);

	}
       	else { 

		/* need to split again */
		overflow(split_parent, over_level-1, old_level, node2, root);

	}

  }



  return;

} /* adjust_tree */


/*
  function : void choose_leaf_level(node_type **node_found, node_type *current_node, int 
             current_level, node_type *inserted_node, int desired_level) 
  purpose  : to choose the leaf node specified by the leaf level
  parameter: node_type **node_found  - the node to be found as a a leaf node
             node_type *current_node - the current node with its children to be found
	                               with the best leaf
	     int current_level       - the level of the current node current_node
	     node_type *insert_node  - the node to be inserted
	     int desired_level       - the desired level up to be checked
  return   : none
*/
void choose_leaf_level(node_type **node_found, node_type *current_node, int 
current_level, node_type *inserted_node, int desired_level) 
{
 
  int child_chosen;

  if (current_level == desired_level) {
        *node_found = current_node;
//printf("7\n");

        return;
  }
  
//printf("current_level %d desired_level %d\n", current_level, desired_level);

//printf("current_node->ptr[0]->ptr[0] %d\n", current_node->ptr[0]->ptr[0]);
  if (current_node->ptr[0]->ptr[0]->attribute != LEAF) {
  
//printf("8\n");
        child_chosen = least_area_enlarge(current_node, inserted_node);
   
  }
  else {
        
//printf("9\n");
        child_chosen = least_overlap_enlarge(current_node, inserted_node);
  
  }

//printf("5\n");

  current_node = current_node->ptr[child_chosen];
//printf("current_level %d desired_level %d\n", current_level, desired_level);
  choose_leaf_level(node_found, current_node, current_level+1, inserted_node, desired_level);

  
  return;
                        
} /* choose_leaf_level */



/*
  function : void reinsert(node_type *over_node, int over_level, node_type *extra_node, 
             node_type *root)  
  purpose  : to reinsert the extra node extra_node into the over node over_node at the level
             over_level given with the root node root
  parameter: node_type *over_node  - the node to be overflown
             int over_level        - the level of the over node
	     node_type *extra_node - the extra node to be inserted
	     node_type *root       - the root node
  return   : none
*/
void reinsert(node_type *over_node, int over_level, node_type *extra_node, 
node_type *root) 
{
  node_type *node_found;
  node_type **overnode;
  double *value; 
  int *sorted_index;