btree.c

btree的实现源代码

				Debug("Couldnt write block\n");
				return FAIL;
			}
		}
	}
	btree->vector = -1;
	btree->blocks_to_flush = 0;
	btree->active_node = NULL;
return SUCCESS;
} /* FlushHierarchy*/

/*
// NAME: 	LoadHierarchyNode
//
// DESCRIPTION:	Load a node into hierarchy at the current vector
//
// RETURN:	SUCCESS or FAIL
//
*/
int LoadHierarchyNode(BTREE * btree /* pointer to tree descriptor */,
		             long n /* node number */)
{

	Trace(" LoadHierarchyNode(%x,%ld)\n", (unsigned)btree, n);
	if (btree->vector < -1) {
		Debug("Invalid node vector\n");
		return FAILED;
		}
	++btree->vector;
	/* Want to create really huge b+trees?*/
/* law 2/4/94 */
	if( (btree->vector + 1) > btree->ActiveHeight ){
		btree->hierarchy_list = (struct HierarchyBlock *)
			realloc((void *)btree->hierarchy_list,
				( (btree->ActiveHeight+1)*sizeof(struct HierarchyBlock)) );
		if(btree->hierarchy_list == NULL)
			Debug("Insufficient available memory\n");
		/* new block in hierarchy gets set clean*/
		(btree->hierarchy_list+btree->ActiveHeight)->block_id = -1L;
		(btree->hierarchy_list+btree->ActiveHeight)->state = CLEAN;
		btree->ActiveHeight++;
	}
	if( ((btree->hierarchy_list+btree->vector)->state == DIRTY) && 
		((btree->hierarchy_list+btree->vector)->block_id != n) ){
			if(BfhWriteBlock(btree->bfh,(char*)&((btree->hierarchy_list+(btree->vector))->hierarchy_node), (btree->hierarchy_list+(btree->vector))->block_id) == FAIL){
			Debug("Couldnt write block\n");
			return FAIL;
			}
		}
	if((btree->hierarchy_list+btree->vector)->block_id == n){
		OpenKeyNode( btree,&(btree->hierarchy_list+btree->vector)->hierarchy_node);
		if(btree->blocks_to_flush < (btree->vector + 1))
			btree->blocks_to_flush = (btree->vector + 1);
		return SUCCESS;
		}
	if(BfhReadBlock(btree->bfh,(char *)&(btree->hierarchy_list+btree->vector)->hierarchy_node,n) != 
			SUCCESS){
		btree->active_node = NULL;
		Debug("Couldnt read block\n");
		return FAIL;
		}
	OpenKeyNode( btree,&(btree->hierarchy_list+btree->vector)->hierarchy_node);
	(btree->hierarchy_list+btree->vector)->block_id = n;
	(btree->hierarchy_list+btree->vector)->state = CLEAN;
	if(btree->blocks_to_flush < (btree->vector + 1))
		btree->blocks_to_flush = (btree->vector + 1);
	return SUCCESS;
} /* LoadHierarchyNode*/
	
/*
// NAME:	Parent
//
// DESCRIPTION:	Move up the hierarchy and make the parent node the new active
//		node.
//
// RETURN:	Pointer to the parent node
//
*/
static struct Node * Parent(BTREE * btree /* pointer to tree descriptor */)
{
	Trace("Parent(%x)\n", (unsigned)btree);
	if( btree->vector < 1 )
		return NULL;
	--btree->vector;
	OpenKeyNode( btree,&(btree->hierarchy_list+btree->vector)->hierarchy_node);
	return &((btree->hierarchy_list+btree->vector)->hierarchy_node);
}

/*
// NAME:	KeyGroupSize
//
// DESCRIPTION:	Provides a means to determine the size of a key group
//
// RETURN:	integer size of the key group
//
*/
int KeyGroupSize(BTREE * btree /* pointer to tree descriptor */,
	         struct KeyGroup * ks /* An encapsolated key */)
{
	int i;

	Trace("KeyGroupSize(%x,%x)\n", (unsigned)btree, (unsigned)ks);
	i = sizeof(long) + sizeof(ks->KeyData);
	switch(btree->type_of_key){
		case VAR_LNG_KEY:
			i+=(int)ks->k.key[0]+1;
/* law fix 1/29/94 */
#ifdef ALIGN2
                        	i += ( 2 - ( (i+2) % 2 ) );
#endif
#ifdef ALIGN4
                        	i += ( 4 - ( (i+4) % 4 ) );
#endif
			break;

		case FIX_LNG_KEY:
		case LONG_KEY:
		case DOUBLE_KEY:
			i+=btree->fix_lng_key_lng;
			break;
		default:
			Debug("Invalid KeyType\n");
	}
	return i;
}
	
/* HERE --- can't allow this to calloc memory junk */
/*
// NAME:	CopyKey
//
// DESCRIPTION:	Copies the active_key into a store area, and returns a pointer
//		to the area.  Calling programs cannot then corrupt the key.
//
// RETURN:	pointer to a key group
//
struct KeyGroup * CopyKey(BTREE * btree )
{
	Trace("CopyKey(%x)\n", (unsigned)btree);
	if(btree->key_copy == NULL){
		btree->key_copy = (struct KeyGroup *)calloc(1,sizeof(struct KeyGroup));
		if(btree->key_copy == NULL){
			Debug("Insufficient available memory\n");
		}
	}
	mv_mem((char *)btree->active_key,(char *)btree->key_copy,KeyGroupSize(btree,btree->active_key));
	return btree->key_copy;
}
*/

/*
// NAME:	InsertNodeKeyGroup
//
// DESCRIPTION:	Submit a key group for insert into a node.  If the node
//		is too full to accept the key, return FAIL, otherwise
//		insert at the current position in the node.
//
// RETURN:	SUCCESS or FAIL.  A full node returns FAIL, while anything
//		else inserts and returns SUCCESS. 
//
*/
static int  InsertNodeKeyGroup(BTREE * btree /* pointer to tree descriptor */,
	   		struct KeyGroup * kg /* An encapsolated key */)
{
	int i,active_posn;

	Trace("InsertNodeKeyGroup(%x,%x)\n",
		(unsigned)btree, (unsigned)kg);
	i = KeyGroupSize(btree,kg);
	if( (btree->block_size - btree->active_node->next_free_position ) < i ) {
		return FAIL;  
	}
	active_posn = (char *)btree->active_key - (char *)btree->active_node;
	mv_mem((char *)btree->active_node + active_posn, 
		(char *)btree->active_node + active_posn + i,
		btree->block_size - i - active_posn);
	mv_mem((char *)kg,(char *)btree->active_node+active_posn,i);
	btree->active_node->total_node_keys ++;
	btree->active_node->next_free_position += i;
	if(btree->vector != -1)
		(btree->hierarchy_list+btree->vector)->state = DIRTY;
	return SUCCESS;
}

/*
// NAME:	InsertSpareKeyGroup
//
// DESCRIPTION:	This function is used to build the spare node.  Called
//		repetively, this function inserts key groups into the 
//		spare node in the sequence provided, at the end of the
//		list.
//
// RETURN:	SUCCESS or FAIL
//
*/
static int  InsertSpareKeyGroup(BTREE * btree /* pointer to tree descriptor */,
			 struct KeyGroup * kg /* An encapsolated key */,
			 struct Node * spare_node /* Pointer to working spare */)
{
	/* insert into the spare node, end position only*/
	int i;

	Trace("InsertSpareKeyGroup(%x,%x,%x)\n", (unsigned)btree, 
		(unsigned)kg, (unsigned)spare_node);
	i = KeyGroupSize(btree,kg);
/*fprintf(stderr, "%d - ( %d + 1 ) <= %d\n",btree->block_size, spare_node->next_free_position, i);*/
	if( (btree->block_size - spare_node->next_free_position ) < i ) {
/*runtime_error(TRACE,__FILE__,__LINE__,"Node too full for insert");*/
		return FAIL;
	}  /* cant stuff any more here*/
	mv_mem((char *)kg,(char *)spare_node+spare_node->next_free_position,i);
	spare_node->total_node_keys ++;
	spare_node->next_free_position += i;
	return SUCCESS;
}


/*
// NAME:	DeleteNodeKeyGroup
//
// DESCRIPTION:	Deletes the current active key by moving down the contents
//		of upper end of the node past the current key to the 
//		current position.
//
// RETURN:	SUCCESS or FAIL
//
*/
static int  DeleteNodeKeyGroup(BTREE * btree /* pointer to tree descriptor */)
{
	int len,i;
	char * cp;

	Trace("DeleteNodeKeyGroup(%x)\n", (unsigned)btree);
	if(btree->key_position > btree->active_node->total_node_keys){
		/* cant delete at node eof*/
		Debug("Invalid delete position\n");
		return FAIL;
	}
	i = KeyGroupSize(btree /* pointer to tree descriptor */,btree->active_key);
	len = ( ((char *)btree->active_node + btree->block_size ) - ( (char *)btree->active_key + i ) );
	cp = (char *)btree->active_key;
	mv_mem(cp + i, cp, len ); 
	--btree->active_node->total_node_keys;
	btree->active_node->next_free_position -= i;
	(btree->hierarchy_list+btree->vector)->state = DIRTY;
	return SUCCESS;
}/*DeleteNodeKeyGroup()*/

/*
// NAME:	Combine
//
// DESCRIPTION: 	This function attempts to combine sibling nodes following a
//		key deletion.  Attempt is first made with the right node, 
//		and if that fails, with the left node.  If it results in the
//		parent root being emptied, a new root node is created.
//		Combine must be called immediately before a return 
//		and after all other processing on the hierarchy is completed.
//
// RETURN:	SUCCESS or FAIL
//
*/
	
static int Combine(BTREE * btree /* pointer to tree descriptor */)
{
	long combine_id;
	int combine_key_count;
	int combine_data_size;
	int combine_key_posn;

	long sibling_id;
	int sibling_key_count;
	int sibling_data_size;
	int sibling_key_posn;
	int sibling_key_size;

	long parent_id;
	int parent_key_count;
	int parent_data_size;
	int parent_key_posn;
	int parent_key_size;
	int parent_pass_through_space;

	int status, i;
	int on_right, parent_is_root;

	struct Node * spare_node;
/* HERE - put the node on the statk??*/
	struct KeyGroup * spare_key;

	struct KeyGroup parent_key;

	int root_exhausted;

	long hold_left;

	Trace("Combine(%x)\n", (unsigned)btree);

	on_right = 0; 
	combine_id = sibling_id = 0L; 
	combine_key_count = parent_key_size = sibling_key_count = 0; 
	root_exhausted = 0; 
	/* save our current id */
	combine_id = (btree->hierarchy_list+btree->vector)->block_id; 
	if(Parent(btree)==NULL) { 
		Debug("Couldnt locate parent\n"); 
		return FAIL; 
	}

	/* Mark the parent as being root node*/
	if(btree->vector == 0){
		parent_is_root = 1;
	}else{
		parent_is_root = 0;
	}

	/* find the right side*/
	status = SUCCESS;
	while(btree->left != combine_id){
		if(btree->active_key->right_node == combine_id)
			on_right = 1;
 		if( (status=IncrementPosition(btree)) != SUCCESS ){
			if(on_right){
				break;
			}
 			Debug("Failed to increment\n");
 			return FAIL;
 		}
		on_right = 0;
	} 
	if(on_right){
		/* This is the condition where we are */
		/* dealing with the far right node in a tree*/
		Rewind(btree);
		while(btree->active_key->right_node != combine_id){
 			if( (status=IncrementPosition(btree)) != SUCCESS ){
				Debug("Failed to increment\n");
				return FAIL;
			}
		}
		combine_id = btree->left;
		/* we have now swapped positions and are working with */
		/* a separate set of nodes*/
	}

	/* this would be the parent key*/
	mv_mem((char *)btree->active_key, (char *)&parent_key, 
		KeyGroupSize(btree,btree->active_key));
	parent_key_size = KeyGroupSize(btree,btree->active_key);
	sibling_id = btree->active_key->right_node;
	if( (btree->vector == 0) && (btree->active_node->total_node_keys == 1))
		root_exhausted = 1;

	/* --- we have our left and right sides*/

	/* get left side data*/
	if( LoadHierarchyNode( btree,combine_id ) == FAIL){ 
		Debug("Cant load node\n");
		return FAIL;
	}
	/* begin building the spare node*/
	spare_node = (struct Node *)malloc(sizeof(struct Node) );
/*fprintf(stderr, "%ld\n", (long)spare_node);*/
	if(spare_node == NULL){
		Debug("Insufficient available memory\n");
	}
	mv_mem( (char *)btree->active_node, (char *)spare_node, sizeof(struct Node) );

	/* collect information*/
	combine_key_count = btree->active_node->total_node_keys;
	combine_key_posn =  btree->active_node->next_free_position;
	combine_data_size = btree->active_node->next_free_position - FirstKeyOffset;

	if(Parent(btree)==NULL){
		Debug("Couldnt locate parent\n");
		return FAIL;
	}
	parent_key_count = btree->active_node->total_node_keys;
	parent_key_posn =  btree->active_node->next_free_position;
	parent_data_size = btree->active_node->next_free_position - FirstKeyOffset;
	parent_id = (btree->hierarchy_list+btree->vector)->block_id; 
	parent_pass_through_space = KeySpace - parent_data_size + 
		parent_key_size;

	/* get right side data*/
	if( LoadHierarchyNode( btree,sibling_id ) == FAIL){ 
		Debug("Cant load node\n");
		free((void*)spare_node);
		return FAIL;
	}
	sibling_key_count = btree->active_node->total_node_keys;
	sibling_key_posn =  btree->active_node->next_free_position;
	sibling_data_size = btree->active_node->next_free_position - FirstKeyOffset;
	sibling_key_size = KeyGroupSize(btree,btree->active_key);
	parent_key.right_node = btree->left;

	/* have we been wasting our time*/
	if(
		/* it is too big to combine*/
	((combine_data_size+parent_key_size+sibling_data_size) > KeySpace ) ||
		/* or, it is a variable length node and there wouldn't be */
		/* space in the node if combined, to fit in an extra key*/
	( (btree->type_of_key == VAR_LNG_KEY) && 
	  ((combine_data_size+parent_key_size+sibling_data_size) > 
		(( KeySpace / 5 ) * 4)))
	)
	
	{
		/* then lets shift left*/

		if (	

			/* if we have keys to shift*/
		   (    sibling_key_count > 2) &&

			/* and it would balance*/
		   (	sibling_key_count > combine_key_count ) &&

			/* and at least 1/5 th the available space is there*/
			/* to accept a shifted key*/
		   (    combine_data_size  < (( KeySpace / 5 ) * 4 )) &&

			/* and if variable length keys, the sibling*/
			/* key can fit into the parent*/
		   ( ! ( (btree->type_of_key == VAR_LNG_KEY ) &&
		    (  (sibling_key_size+1) > parent_pass_through_space ))) 
		)

		{
			/* steal - shift some of the sibling to the*/
			/* combine node*/
			/* - we have the parent key, and are at the */
			/* sibling.  We need the first sibling key in */
			/* the parent, and the parent key in the combine*/
			free((void *)spare_node);
			Rewind(btree);
			spare_key = (struct KeyGroup *)
				malloc(sizeof(struct KeyGroup));
			if(spare_key == NULL){
				Debug("Insufficient available memory\n");
			}