xbuild.c

xtree程序实现

  int i, start, stop;

  // **** Ray has fixed the following bugs
  // **** from "sizeof(double) * M+1" to "sizeof(double) * (M+1)"
  // **** from "sizeof(int) * M+1" to "sizeof(int) * (M+1)"
  value = (double *)malloc(sizeof(double) * (M+1));
  sorted_index = (int *)malloc(sizeof(int) * (M+1));

  overnode = (node_type **)malloc((M+1) * sizeof(node_type *));
  for (i=0; i<M; i++) {
        overnode[i] = over_node->ptr[i];
  }

  overnode[M] = extra_node;
  overnode[M]->parent = over_node;

  for (i=0; i<M+1; i++) {
	value[i] = Dist2(overnode[i], over_node);
	sorted_index[i] = i;
  }

  quicksort(sorted_index, value, 0, M);

  for (i=0; i<dim; i++) {
	over_node->a[i] = overnode[sorted_index[0]]->a[i];
	over_node->b[i] = overnode[sorted_index[0]]->b[i];
  }
  over_node->ptr[0] = overnode[sorted_index[0]];

//printf("1\n");

  stop = M+1-reinsert_p;

  for (i=1; i<stop; i++) {
	over_node->ptr[i] = overnode[sorted_index[i]];
	cal_MBR_node_node(over_node->a, over_node->b, over_node, overnode[sorted_index[i]]);
  }
  for (i=stop; i<M; i++)
	over_node->ptr[i] = NULL;

  over_node->vacancy = reinsert_p - 1;

  adjust_MBR_delete(over_node);

  start = M + 1 - reinsert_p;

  for (i=start; i<M+1; i++) {

	node_found = root;
	
	choose_leaf_level(&node_found, root, 0, overnode[sorted_index[i]], over_level+extra_level);
//printf("2\n");
 
	/* Test whether the node has room or not */
	if(node_found->vacancy!=0) {
 
		/* have room to insert the entry */
//printf("3\n");

		overnode[sorted_index[i]]->parent = node_found;

	        node_found->ptr[M - node_found->vacancy] = overnode[sorted_index[i]];

        	node_found->vacancy--;

	        adjust_MBR(overnode[sorted_index[i]]);
//printf("4\n");
	}
	else {

		overflow(node_found, over_level, over_level, overnode[sorted_index[i]], root);

	}

  }        


  return;
  
} /* reinsert */




/*
  function : void adjust_tree_X(node_type *over_node, node_type *extra_node, node_type *root)
  purpose  : to adjust the tree where the additional super node is created in the over_node
  parameter: node_type *over_node  - the over node
             node_type *extra_node - the extra node to be added
	     node_type *root       - the root node
  return   : none
*/
// *** Ray added this function
//create the supernode on the X-tree
void adjust_tree_X(node_type *over_node, node_type *extra_node, node_type *root)
{
	node_type *parentNode;
	node_type **temp;

	int i;

	if (over_node->attribute == ROOT)
	{
		temp = root->ptr;

		// Increment the snode Size
		root->snodeSize++;

		// Assign the children
		root->ptr = (node_type **) malloc(sizeof(node_type *)*root->snodeSize*M);

		for (i = 0; i < (root->snodeSize-1)*M; i++)
		{
			temp[i]->parent = root;
			root->ptr[i] = temp[i];
if (root->ptr[i] == NULL) printf("  ########## adjust_tree_X1:%d\n", i);
		}
		root->ptr[(root->snodeSize-1)*M] = extra_node;

		//parent of extra node
		extra_node->parent = root;
		
		//attriubet of extra node
		//extra_node->attribute = NODE;
		
		// update the vacnacy
		root->vacancy = M-1;

		// update the MBR
		cal_MBR_node_node(root->a, root->b, root, extra_node);
		adjust_MBR(root);
	}
	else
	{
		// the super node is at the intermediate node

		parentNode = over_node->parent;
		
		temp = over_node->ptr;
		
		// Increment the snode Size
		over_node->snodeSize++;
		
		// Asign the children
		over_node->ptr = (node_type **) malloc(sizeof(node_type *)*over_node->snodeSize*M);
		
		for (i = 0; i < (over_node->snodeSize-1)*M; i++)
		{
			temp[i]->parent = over_node;
			over_node->ptr[i] = temp[i];
		}
		over_node->ptr[(over_node->snodeSize-1)*M] = extra_node;
//printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");		
		//parent of extra node
		extra_node->parent = over_node;
		
		//attribute of the extra node
		//extra_node->attribute = NODE;
		
		// update the vacancy
		over_node->vacancy = M-1;
		
		
		// update the MBR
		cal_MBR_node_node(over_node->a, over_node->b, over_node, extra_node);
		adjust_MBR(over_node);
	}


//printf("*****\n");
/*
	parentNode = over_node->parent;

	temp = over_node->ptr;

	// Increment the snode size
	over_node->snodeSize++;

	// Assign the children
	over_node->ptr = (node_type **) malloc(sizeof(node_type *)*over_node->snodeSize*M);

	for (i = 0; i < (over_node->snodeSize-1)*M; i++)
	{
		temp[i]->parent = over_node;
		over_node->ptr[i] = temp[i];
	}
	over_node->ptr[(over_node->snodeSize-1)*M] = extra_node;

	//parent of extra node
	extra_node->parent = over_node;

	// update the vacancy
	over_node->vacancy = M-1;

	// update the MBR
	cal_MBR_node_node(over_node->a, over_node->b, over_node, extra_node);
	adjust_MBR(over_node);
*/
}




/*
  function : void overflow(node_type *over_node, int over_level, int old_level, node_type
             *extra_node, node_type *root)
  purpose  : to handle the situation of the overflow node over_node with the over node level
             over_level and the old over node level when the extra node extra_node is added
  parameter: node_type *over_node  - the overflow node
             int over_level        - the level of the overflow node
	     node_type *extra_node - the extra node to be added into the overflow node
	     node_type *root       - the root node
  return   : none
*/
void overflow(node_type *over_node, int over_level, int old_level, node_type
*extra_node, node_type *root)
{
  node_type *node1, *node2;

  // *** Ray modified
/*  if (over_level < old_level && over_level != 0) {
	reinsert(over_node, over_level, extra_node, root);

  }
  else {

	tree_node_allocate(&node1);
	tree_node_allocate(&node2);

        split(over_node, extra_node, node1, node2);

        adjust_tree(over_node, over_level, old_level, node1, node2, root);

//printf("overflow, go out adjust, extra_node->id %d\n", extra_node->id);


  }
*/  

    // *** Ray changed
	tree_temp_node_allocate(&node1, over_node->snodeSize);
	tree_temp_node_allocate(&node2, over_node->snodeSize);

    if (split(over_node, extra_node, node1, node2) == TRUE)
	{

        adjust_tree(over_node, over_level, old_level, node1, node2, root);  
	}
	else
	{
		//create supernode
		adjust_tree_X(over_node, extra_node, root);
	}
  
  return;
  
}


/*
  function : void insert_node(node_type *root, float *data, int seq_id)
  purpose  : to insert the data into the X-tree provided with 
  parameter: node_type *root - the root node
             float *data     - the array to store the data
	     int seq_id      - the id of the data
  return   : none
*/
void insert_node(node_type *root, float *data, int seq_id)
{
  node_type *node_found, *new_node, *data_node;
  int level_found;


  int i;

  /******/
  /* I1 */
  /******/


  node_found = root;
  extra_level=0;

  tree_node_allocate(&data_node);
  for (i=0; i<dim; i++) {
	data_node->a[i] = data[i];
	data_node->b[i] = data[i];
  }
  level_found = choose_leaf(&node_found, root, 0, data_node);
  /* Now, node_found is the pointer to the leaf chosen */


  /******/
  /* I2 */
  /******/
  
  /********************************************************/
  /* Add record to leaaf node:                            */
  /* If L has room for another entry, install the entry   */
  /* Otherwise invoke split() to split the node */
  /********************************************************/  
  
  /* Make a leaf node */

  tree_node_allocate(&new_node);


  for(i=0; i < dim; i++) { 
       	new_node->a[i]=data[i];
       	new_node->b[i]=data[i];
  }
  new_node->id = seq_id;		//data[dim] is the seq_id   
  new_node->attribute=LEAF;
  new_node->vacancy=M;
  new_node->parent=node_found;
  for(i=0; i < M; i++)
     new_node->ptr[i]=NULL;

  /* Test whether the node has room or not */
  if(node_found->vacancy!=0) { 



	/* have room to insert the entry */

	// *** Ray changed
	//node_found->ptr[M - node_found->vacancy] = new_node;
	node_found->ptr[M*node_found->snodeSize - node_found->vacancy] = new_node;

      	node_found->vacancy--;
     
	adjust_MBR(new_node);

  }
  else {

	overflow(node_found, level_found, level_found+1, new_node, root);

  }


  return;

} /* insert_node */
  





/*
  function : void build_tree(node_type **root, float **data, int no_data)
  purpose  : to build an X-tree (provided with the root) from the data set given with the 
             no. of data
  parameter: node_type **root - the root node
             float **data     - the array of the data (shown in dimension)
	     int no_data      - the no. of data
  return   : none
*/
/********************/
/* build_tree():    */
/* build the R-tree */
/********************/
      
void build_tree(node_type **root, float **data, int no_data)
{ 
  int i, j;


  /* make tree root node first */

  tree_node_allocate(root);

  for(i=0; i < dim; i++) { 
	(*root)->b[i] = (float)(-1 * INT_MAX);
       	(*root)->a[i] = (float)(INT_MAX);
  }
  (*root)->id = -3;		//NO_ID
  (*root)->attribute=ROOT;
  (*root)->vacancy=M;   
  (*root)->parent=NULL; 
  // *** Ray added
  (*root)->snodeSize = 1;
  // *** Ray changed
  //for(j=0; j < M; j++)
  for(j=0; j < M*(*root)->snodeSize; j++)
     	(*root)->ptr[j]=NULL;


  /* add data to the tree */
  for(i=0; i<no_data; i++) { 

/*
#ifdef DEBUG
if (i+1%1000==0)
	printf("insert data %d\n", i+1);
#endif

if (i == 131)
{
	printf("**** here\n");
}
if (i == 236)
{
	printf("**** here\n");
}
if (i == 243)
{
	printf("**** here\n");
}
if (i == 398)
{
	printf("**** here\n");
}
*/
if (i == 331)
{
	printf("*** here\n");
}
if (i == 332)
{
	printf("*** here\n");
}
if (i == 220)
{
	printf("*** here\n");
}
if (i == 4127)
{
	printf("*** here\n");
}
printf("///////insert new->id %d\n", i);
if (i == 492)
{
	printf("*** here\n");
}

      	insert_node(*root, data[i], i);  // i is the seq id.

printf("      %d\n", hasInterElement(*root, 5));

	free(data[i]);
  }

  free(data);

} /*build_tree */



/*
  function : int make_data(char *positionfile, float ***data)
  purpose  : to read the file name positionfile and put the data which has
             been read into the variable data
  parameter: char *positionfile - the name of the file 
             float ***data      - the array of data to be put
  return   : int - no. of data
*/
int make_data(char *positionfile, float ***data)
{ 
  int no_data;
  int i,j;
  FILE *fp_position;

  fp_position=fopen(positionfile,"r");  

  no_data = no_histogram;

  (*data) = (float **)malloc(sizeof(float*) * no_data);
  for(i=0; i<no_data; i++)
        (*data)[i] = (float *)malloc(sizeof(float) * dim);

  for(i=0; i<no_data; i++)
	for (j=0; j<dim; j++)
		fscanf(fp_position,"%f",&((*data)[i][j]));

  fclose(fp_position);

  return(no_data);

} /* make_data */




/*
  function : void write_leaf_node(node_type *node, FILE *fp)
  purpose  : to write the information of the leaf node to the file pointer fp
  parameter: node_type *node - the leaf node to be written
             FILE *fp        - the file pointer pointing to the file
  return   : none
*/
void write_leaf_node(node_type *node, FILE *fp)
{
  int i;
               
  for (i = 0; i<dim; i++)
        fprintf(fp, "%f\n", (node->a)[i]);
 
  for (i = 0; i<dim; i++)
        fprintf(fp, "%f\n", (node->b)[i]);
 
  fprintf(fp, "%d\n", node->attribute);
  fprintf(fp, "%d\n", node->id);
  fprintf(fp, "%d\n", node->vacancy);
fprintf(filePtrID, "%d\n", node->id);
  return;

}



/*
  function : void write_inter_node(node_type *node, FILE *fp)
  purpose  : to write the internal node to the file pointer fp
  parameter: node_type *node - the internal node to be written to the file
             FILE *fp        - the file pointer pointing to the file to be written
  return   : none
*/
void write_inter_node(node_type *node, FILE *fp)
{
  int i, count;

  for (i = 0; i<dim; i++) 
	fprintf(fp, "%f\n", (node->a)[i]);
	//fprintf(fp, "%f\n", 0.0f);

  for (i = 0; i<dim; i++)  
        fprintf(fp, "%f\n", (node->b)[i]);
		//fprintf(fp, "%f\n", 1.0f);

  fprintf(fp, "%d\n", node->attribute);
  fprintf(fp, "%d\n", node->vacancy);
  // **** Ray added
  fprintf(fp, "%d\n", node->snodeSize);
  if (node->snodeSize > 1) {
	  printf("**** has supernode (%d)\n", node->snodeSize);
	  printf("     vacancy (%d)\n", node->vacancy );
  }

  // **** Ray changed
  //count = M - node->vacancy;
  count = M*node->snodeSize - node->vacancy;
  for (i=0; i<count; i++) {
	if (node->ptr[i]->attribute != LEAF)
		write_inter_node(node->ptr[i], fp);
	else
		write_leaf_node(node->ptr[i], fp);
  }

  return;

}
  


/*
  function : void save_xtree(node_type *root)
  purpose  : to save the xtree (starting at the root) to the file named SAVE_XTREE_FILE
  parameter: node_type *root - the root node of the X-tree
  return   : none
*/
void save_xtree(node_type *root)
{
  FILE *fp;

  fp = fopen(SAVE_XTREE_FILE, "w");
  
  write_inter_node(root, fp);

  fclose(fp);
 
  return;

}


// Main Program
int main(void)
{ 

  int no_data;
  float **data;
  config_type config;
  node_type *root;


filePtrID = (FILE *) fopen("id.txt", "w"); 

  initialize(&config);   

  no_data=make_data(config.positionfile, &data);

  build_tree(&root, data, no_data);
  save_xtree(root);

fclose(filePtrID);

  return(0);  
} /* main */