btree.c

btree的实现源代码

			mv_mem((char *)btree->active_key, (char *)spare_key, 
				KeyGroupSize(btree,btree->active_key));
			/* got the first sibling key, now remove it*/
                	if( DeleteNodeKeyGroup(btree) == FAIL ){
                       		Debug("Key not deleted \n");
				return FAIL;
                	}
			/* have both keys, now we need to shuffle the */
			/* pointers*/
			/* assuming active node is the sibling*/
			parent_key.right_node = btree->active_node->nodeblock.left_node;
			btree->active_node->nodeblock.left_node = spare_key->right_node;
			spare_key->right_node = sibling_id;
        		(btree->hierarchy_list+btree->vector)->state = DIRTY;

			/* subsitute in the parent the sibling key*/
			if(Parent(btree)==NULL){
				Debug("Couldnt locate parent\n");
				free((void *)spare_key);
				return FAIL;
			}
			while(btree->active_key->right_node != sibling_id){
 				if( (status=IncrementPosition(btree)) != SUCCESS ){
					Debug("Failed to increment\n");
					free((void *)spare_key);
					return FAIL;
				}
			}
       		        if( DeleteNodeKeyGroup(btree) == FAIL ){
	       	                Debug("Key loss deleting during split\n");
				free((void *)spare_key);
				return FAIL;
       		        }
/* HERE var lng poten fail */
                	if( InsertNodeKeyGroup(btree,spare_key) == FAIL){
                        	Debug("Couldnt insert replacement key\n");
                        	free((void *)spare_key);
                        	return FAIL;
                        }
			free((void *)spare_key);
			if( LoadHierarchyNode( btree,combine_id ) == FAIL){ 
				Debug("Cant load node\n");
				return FAIL;
			}
                	if(btree->active_node->total_node_keys > 0){
                        	for(;;){
                                	status = Compare(btree,(union Key *)
						parent_key.k.key);
                                	if(status != 1 )
                                        	break;
                                	if((status = IncrementPosition(btree)) != 
						SUCCESS){
                                        	break;
                                	}
                        	}
                	}
                	if(InsertNodeKeyGroup(btree,&parent_key) == FAIL){
                        	Debug("lost a key(s)\n");
                	}
			return SUCCESS;
		} 
		/* then lets shift right*/
		
		if (	
			/* if we have keys to shift*/
			( combine_key_count > 2) &&

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

			/* and at least 1/5 th the available space is there*/
		   (    sibling_data_size  < (( KeySpace / 5 ) * 4 ))
		   )
		{

			free((void *)spare_node);
			if(Parent(btree)==NULL){
				Debug("Couldnt locate parent\n");
				free((void *)spare_key);
				return FAIL;
			}
			if( LoadHierarchyNode( btree,combine_id ) == FAIL){ 
				Debug("Cant load node\n");
				return FAIL;
			}
			Rewind(btree);
			spare_key = (struct KeyGroup *)
				malloc(sizeof(struct KeyGroup));
			if(spare_key == NULL){
				Debug("Insufficient available memory\n");
			}
			for(i=1;i<combine_key_count;i++){
				if( IncrementPosition(btree) != SUCCESS){
					free((void *)spare_key);
					return FAIL;
				}
			}

			/* and if variable length keys, the sibling*/
			/* key can fit into the parent*/
			if( (btree->type_of_key == VAR_LNG_KEY) &&
		    	    (  (KeyGroupSize(btree,btree->active_key)+1) > 
					parent_pass_through_space )
			  ){
				return FAIL;
			}
			mv_mem((char *)btree->active_key, (char *)spare_key, 
				KeyGroupSize(btree,btree->active_key));
			/* got the last combine key, now remove it*/
                	if( DeleteNodeKeyGroup(btree) == FAIL ){
                       		Debug("failed to delete key\n");
				return FAIL;
                	}
			/* have both keys, now we need to shuffle the */
			/* pointers*/
			/* assuming active node is the sibling*/
			hold_left = spare_key->right_node;
			spare_key->right_node = sibling_id;

        		(btree->hierarchy_list+btree->vector)->state = DIRTY;

			/* subsitute in the parent the sibling key*/
			if(Parent(btree)==NULL){
				Debug("Couldnt locate parent\n");
				free((void *)spare_key);
				return FAIL;
			}
			while(btree->active_key->right_node != sibling_id){
 				if( (status=IncrementPosition(btree)) != SUCCESS ){
					Debug("Failed to increment\n");
					free((void *)spare_key);
					return FAIL;
				}
			}
       		        if( DeleteNodeKeyGroup(btree) == FAIL ){
	       	                Debug("failed to delete key\n");
				free((void *)spare_key);
				return FAIL;
       		        }
/* HERE var lng poten fail */
                	if( InsertNodeKeyGroup(btree,spare_key) == FAIL){
                        	Debug("Couldnt insert replacement key\n");
                        	free((void *)spare_key);
                        	return FAIL;
                        }
			free((void *)spare_key);
			if( LoadHierarchyNode( btree,sibling_id ) == FAIL){ 
				Debug("Cant load node\n");
				return FAIL;
			}
			parent_key.right_node = btree->active_node->nodeblock.left_node;
			btree->active_node->nodeblock.left_node = hold_left;
	
                	if(InsertNodeKeyGroup(btree,&parent_key) == FAIL){
                        	Debug("lost a key(s)\n");
                	}
/*Debug(btree->active_node, 0);*/
			return SUCCESS;
		}

		if 	((combine_key_count < 2) || (sibling_key_count < 2))
		{
/*
fprintf(stderr, "UNDERFLOW\n");
fprintf(stderr, "combine_id %ld combine_key_count %d combine_data_size %d \ncombine_key_posn %d sibling_id %ld sibling_key_count %d \nsibling_data_size %d sibling_key_posn %d parent_id %ld parent_key_count %d \nparent_data_size %d parent_key_posn %d\n",
combine_id, 
combine_key_count, combine_data_size, combine_key_posn, 
sibling_id, sibling_key_count, sibling_data_size, sibling_key_posn,
parent_id, parent_key_count, parent_data_size, parent_key_posn);
*/
			free((void *)spare_node);
			return FAIL;
		}
		free((void *)spare_node);
		/* It is success because it is sufficiently well balanced*/
		/* anyway*/
		return SUCCESS;
	}

	/* put it all together*/
        if( (status = InsertSpareKeyGroup(btree,&parent_key,spare_node)) == FAIL ){
                free( (void *)spare_node);
                Debug("Failed to Insert\n");
                return FAIL;
        }
        mv_mem( ((char *)btree->active_node)+FirstKeyOffset,
                ((char *)spare_node)+spare_node->next_free_position,
                sibling_data_size );
	spare_node->total_node_keys+=sibling_key_count;
	spare_node->next_free_position+=sibling_data_size;

	/* position to the results node*/
	if(Parent(btree)==NULL){
		Debug("Couldnt locate parent\n");
		free((void *)spare_node);
		return FAIL;
	}
	if( LoadHierarchyNode( btree,combine_id ) == FAIL){ 
		Debug("Cant load node\n");
		free((void *)spare_node);
		return FAIL;
	}

	/* replace the data with the combined node data*/
        mv_mem((char *)spare_node,
               (char *)btree->active_node,
               sizeof(struct Node));
        (btree->hierarchy_list+btree->vector)->state = DIRTY;
	BfhFreeBlock(btree->bfh,sibling_id);

	free((void *)spare_node);
        if(root_exhausted){
                /* then we have a new root node, the key we just*/
                /* combined*/
		long free_block_id;

                (btree->hierarchy_list+0)->block_id = -1L;
                (btree->hierarchy_list+0)->state = CLEAN;
                /* make it the root node*/
                free_block_id=(btree->hierarchy_list+btree->vector)->block_id;
                (btree->hierarchy_list+btree->vector)->block_id = btree->rootnode;
                if(BfhFreeBlock(btree->bfh, free_block_id ) == FAIL){
                        Debug("Cant free block\n");
                        return FAIL;
                }
                btree->search_levels --;
        }else{
		/* we still have a key in the root that needs to */
		/* be removed*/
		if(Parent(btree)==NULL){
			Debug("Couldnt locate parent\n");
			return FAIL;
		}
		while(btree->active_key->right_node != sibling_id){
 			if( (status=IncrementPosition(btree)) != SUCCESS ){
				Debug("Failed to increment\n");
				return FAIL;
			}
		}
                if( DeleteNodeKeyGroup(btree) == FAIL ){
                        Debug("Key loss deleting during split\n");
			return FAIL;
                }
	}

	FlushHierarchy(btree);
	return SUCCESS;
} /* end Combine()*/


/*
// NAME:	RemoveNodeKeyGroup
//
// 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, and then inserting into the position
//		the next greater key in the tree (leaf position).
//
// RETURN:	SUCCESS or FAIL
//
*/
static int  RemoveNodeKeyGroup(BTREE * btree /* pointer to tree descriptor */)
{
	struct KeyGroup delete_key;
	struct KeyGroup replacement_key;
	int space_available;
	int saved_vector;
	long right_pointer;
	int shift_vector;

	shift_vector = 0;

	Trace("RemoveNodeKeyGroup(%x)\n", (unsigned)btree);
	/* keep important info*/
	mv_mem((char *)btree->active_key, (char *)&delete_key, 
		KeyGroupSize(btree,btree->active_key));
	saved_vector = btree->vector;
	right_pointer = btree->active_key->right_node;

	/* How much space do we have for the replacement key?*/
	space_available = KeyGroupSize(btree,btree->active_key);
	space_available += btree->block_size - btree->active_node->next_free_position;

	if(btree->active_key->right_node == -1L){
		Debug("remove operation for interior nodes\n");
		return FAIL;
	}

	/* Get the leaf key next in the node*/
	if(LoadHierarchyNode(btree,btree->active_key->right_node) == SUCCESS){
		while(btree->left != -1L){
			if(LoadHierarchyNode(btree,btree->left) != SUCCESS){
				Debug("Failed to load node\n");
				return FAIL;
			}
		}
	}else{
		Debug("Failed to load node\n");
		return FAIL;
	}
        if(btree->active_key->right_node != -1L){
/*Debug(btree->active_node, 0);*/
                Debug("Unbalanced node\n");
                return FAIL;
        }
/*	// will the key we are looking at fit??*/
/*	if( KeyGroupSize(btree,btree->active_key) > space_available ){*/
/*		//boink*/
/*if(DEVELOPMENT)fprintf(stderr,"key too big\n");*/
/*		return FAIL;*/
/*	}*/

	/* save it*/
	mv_mem((char *)btree->active_key, 
		(char *)&replacement_key, KeyGroupSize(btree,btree->active_key));

	/* delete it*/
	DeleteNodeKeyGroup(btree);

	/* It may be necessary to adjust the entire tree*/
	CombineAll(btree);   /* starts with a leaf shift which will */
			/* take care of empty leaves*/
	/* goback*/
	FlushHierarchy(btree);
        if(LocateExact(btree,(union Key *)&delete_key.k.key) != SUCCESS){
                Debug("Lost key, Couldnt locate key\n");
                return FAIL;
        }

	/* new key points to old key's right side*/
	replacement_key.right_node = btree->active_key->right_node;

	/* remove the original */
	if(DeleteNodeKeyGroup(btree) != SUCCESS){
		Debug("failed to delete key\n");
		return FAIL;
	}

/* insert the key from the leaf*/
/*HERE what if too big?*/
	if ( InsertNodeKeyGroup( btree,&replacement_key ) == FAIL){
		Debug("couldn't insert, better rebuild\n");
		return FAIL;
	}

	return SUCCESS;
}/*RemoveNodeKeyGroup*/


/*
// NAME:	LeftAddress
//
// DESCRIPTION:	Provides the public accessability to the left pointer
//		to the active key.
//
// RETURN:
//
*/
static long LeftAddress(BTREE * btree /* pointer to tree descriptor */)
{
	return btree->left;
}

/*
// NAME:	IncrementPosition
//
// DESCRIPTION:	Move up one position in the current active node.
//
// RETURN:	SUCCESS FAIL NODE_EOF
//
*/
int  IncrementPosition(BTREE * btree /* pointer to tree descriptor */)
{
	/* *** Increment past the last key is allowed in order to add a */
	/* *** key at the end of the key list.  */
	Trace("IncrementPosition(%x)\n", (unsigned)btree);
Trace("");
	if(( btree->key_position + 1 ) > ( btree->active_node->total_node_keys + 1 ) ){
		btree->active_key = NULL;
		return FAIL;
	}
	btree->left = btree->active_key->right_node;
	/* if this is the node eof the active key is invalid*/
	btree->active_key = (struct KeyGroup *)((char *)btree->active_key + KeyGroupSize(btree,btree->active_key));
	btree->key_position ++;
	if( btree->key_position == ( btree->active_node->total_node_keys + 1 ) )
		return NODE_EOF;
	return SUCCESS;
} /* IncrementPosition*/

/*
// NAME:	Rewind
//
// DESCRIPTION:	Rewind the active key to the first position
//
// RETURN:	NONE
//
*/
void  Rewind(BTREE * btree /* pointer to tree descriptor */)
{
	Trace("Rewind(%x)\n", (unsigned)btree);
	btree->left = btree->active_node->nodeblock.left_node;
	btree->key_position = 1;
	btree->active_key = (struct KeyGroup *)((char *)btree->active_node + FirstKeyOffset); 
}

/*
// NAME:	Compare
//
// DESCRIPTION:	Access the installed compare function, and compare the
//		passed key in a union Key to the active key.
//
// RETURN:
//
*/
int   Compare(BTREE * btree /* pointer to tree descriptor */,
	      union Key *value /* An encapsolated key */)
{
	return (*btree->compare_funct)(value,btree->active_key,btree->fix_lng_key_lng);
}

/*
//
// NAME:	Currentkey
//
// DESCRIPTION:	
//
// RETURN:
//
*/
int  Currentkey(BTREE * btree, /* pointer to tree descriptor */
                struct KeyGroup * ckp /* An encapsolated key */ )
{
	Trace("Currentkey(%x,%x)\n", (unsigned)btree, (unsigned)ckp);
	mv_mem((char *)btree->active_key,(char *)ckp,KeyGroupSize(btree,btree->active_key));
return SUCCESS;
}