btree.c

btree的实现源代码

// RETURN:	SUCCESS or FAIL
//
*/

int  DeleteKey (BTREE * btree /* pointer to tree descriptor */,
	        union Key * delete_key /* An encapsolated key */)
{

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

	if( btree->exhausted)
		return FAIL;
	/* we could have eof success fail or near match */
	if(LocateExact(btree,delete_key) != SUCCESS){
		Debug("Couldnt locate key\n");
		return FAIL;
	}

	/* check for leaf*/
	/* delete it and call combine*/
	if( btree->active_key->right_node == -1L){
		if(DeleteNodeKeyGroup(btree) == SUCCESS){
			btree->number_of_keys--;
			if(btree->number_of_keys == 0){
				btree->exhausted = 1;
				btree->search_levels = 0;
                		if(BfhFreeBlock(btree->bfh, btree->rootnode ) 						== FAIL){
		                        Debug("Cant free block\n");
               		         	return FAIL;
                		}
				btree->hierarchy_list->state = CLEAN;
			}else{
				if(btree->vector > 0)
					CombineAll(btree);
			}
			FlushHierarchy(btree);
			return SUCCESS;
		} else {
			Debug("Couldnt delete\n");
			return FAIL;
		}
	}

	/* ----  must be interior node*/
	if(RemoveNodeKeyGroup(btree) != SUCCESS){
		Debug("Coundnt remove the key\n");
		return FAIL;
	}
	btree->number_of_keys--;
	FlushHierarchy(btree);
	return SUCCESS;
} /* operator -=*/

/*
// NAME:    CombineAll
//
// DESCRIPTION:  Calls the Combine() routine from the current vector until the
//              root has been reached
//
// RETURN:     Pointer the the first key group in the tree, or NULL on
//              failure.
//
*/
static void CombineAll(BTREE * btree/* pointer to tree descriptor */)
{
        int status;
	int current;

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

	current = btree->vector;

        while(1){
                status = Combine(btree);
                if(status == FAIL)
                        break;
		btree->vector = current;
                btree->vector --; current --;
                if( !btree->vector )
                        break;
                OpenKeyNode( btree,&(btree->hierarchy_list+btree->vector)->hierarchy_node);
        }

} /* end CombineAll()*/

/*
// NAME:	First
//
// DESCRIPTION:	Locate and return a pointer to the first key group in the
//		tree.
//
// RETURN:	Pointer the the first key group in the tree, or NULL on 
//		failure.
//
*/
struct KeyGroup * First(BTREE * btree /* pointer to tree descriptor */)
{
	long next_node;

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

	if(btree->exhausted)
		return FAIL;
	next_node = btree->rootnode; /* root node */
	FlushHierarchy(btree);
	btree->vector = -1;
	btree->active_key = NULL;
	while(1){
		if(LoadHierarchyNode(btree, next_node ) == FAIL){ 
			Debug("Cant load node\n");
			return NULL;
		}
		if(btree->left == -1L){
			if(btree->active_node->total_node_keys == 0)
				return NULL;
			return (btree->active_key);
			}
		next_node = btree->left;
	}
} /* First*/

/*
// NAME:	Increment
//
// DESCRIPTION:	Increment the internal pointers to the next key in the 
//		tree.	
//
// RETURN:	Pointer to next key group structure in the tree.  
//		NULL on failure
//
*/
struct KeyGroup *  Increment(BTREE * btree /* pointer to tree descriptor */)
{
	long bid;

	Trace("Increment(%x)\n",(unsigned)btree);
	if (btree->exhausted )
		return FAIL;
	if (btree->active_key == NULL)
		return NULL;
	if ((btree->vector == 0) && ( btree->active_node->total_node_keys == 0 )){
		/* a root node can be fully exhausted*/
		btree->active_key = NULL;
		return NULL;
        }
	/* if there is anything here we have to go south*/
	if(btree->active_key->right_node != -1L){
		/* decend into that group*/
		if(LoadHierarchyNode(btree,btree->active_key->right_node)==SUCCESS){
			/* find the lowest key down that side*/
			while(btree->left != -1L){
				if(LoadHierarchyNode(btree,btree->left)!=SUCCESS){
					Debug("Cant load node\n");
					return NULL;
				}
			}
			return (btree->active_key);
		} else { 
			Debug("Cant load node\n");
			return NULL;
			}
	}

	/* otherwise lets try the next key*/
	if (btree->key_position < btree->active_node->total_node_keys){
		if(IncrementPosition(btree)==SUCCESS)
			return (btree->active_key);
		else { 
			Debug("Couldnt increment\n");
			return NULL;
			}
	}

	/* if already on the last key*/
	else {
		int stat;
		do	{
			/* keep the id of the present node*/
			bid = (btree->hierarchy_list+btree->vector)->block_id;
			if(Parent(btree)==NULL){
				Debug("Cant find parent\n");
				return NULL;
			}
			/* look for the key that has our child*/
			while(btree->left != bid){
				if((stat=IncrementPosition(btree))==FAIL){
					Debug("Cant increment\n");
					return NULL;
				}
			} 
			/* if we have a valid position return key*/
			if(btree->key_position < ( btree->active_node->total_node_keys + 1) ){
				return (btree->active_key);
				}
			/* if we are at eof we try again or quit if we have*/
			/* run out*/
		}while (btree->vector > 0);
		Debug(NULL);
		return NULL;
	}
} /* operator ++*/

/*
// NAME:	Last
//
// DESCRIPTION:	Find the last key in the tree.
//
// RETURN:	Pointer to last key group structure in the tree.  
//		NULL on failure
//
*/
struct KeyGroup *  Last(BTREE * btree /* pointer to tree descriptor */)
{
	long next_node;
	int i;
	next_node = btree->rootnode; /* root node */

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

	if(btree->exhausted)
		return FAIL;
	FlushHierarchy(btree);
	btree->vector = -1;
	while(1){
		if(LoadHierarchyNode(btree, next_node ) == FAIL){ 
			Debug("Couldnt load node\n");
			return NULL;
		}
		if(btree->active_node->total_node_keys == 0)
			return NULL;
		/* get the rightmost key*/
		for(i = 0; i < btree->active_node->total_node_keys-1;i++){
			if(IncrementPosition(btree)!=SUCCESS)
				return NULL;
		}
		if(btree->active_key->right_node == -1L){
			return (btree->active_key);
			}
		next_node = btree->active_key->right_node;
	}
} /* Last*/

/*
// NAME:	Decrement
//
// DESCRIPTION:	Decrement the internal pointers to the next key in the 
//		tree.	
//
// RETURN:	Pointer to previous key group structure in the tree.  
//		NULL on failure
*/
struct KeyGroup *  Decrement (BTREE * btree /* pointer to tree descriptor */)
{
	long bid;
	int i,hold_posn;


	Trace("Decrement(%x)\n", (unsigned)btree);
	if(btree->exhausted)
		return FAIL;
	/* if there is anything here we have to go south*/
        if(btree->active_key == NULL)
		return NULL;
	if(btree->left != -1L){
		/* decend into that group*/
		if(LoadHierarchyNode(btree,btree->left)==SUCCESS){
			/* find the highest key down that side*/
			while(1){
				for(i = 0; i < btree->active_node->total_node_keys-1;
						i++){
					if(IncrementPosition(btree)!=SUCCESS)
						return NULL;
				}
				if(btree->active_key->right_node == -1L)
					return (btree->active_key);
				if(LoadHierarchyNode(btree,btree->active_key->right_node)!=
						SUCCESS){
					Debug("Couldnt load node\n");
					return NULL;
				}
			}
		} else {
			return NULL;
		}
	}
	/* otherwise get prev key in same node*/
	hold_posn = btree->key_position;
	if(hold_posn == 1){
		if(btree->vector == 0)
			return NULL; /* no previous keys*/
		while(1){
			bid = (btree->hierarchy_list+btree->vector)->block_id;
			if(Parent(btree)==NULL){
				Debug("Couldnt locate parent\n");
				return NULL;
			}
			if(btree->left == bid){
				if(btree->vector == 0)
					return NULL;
				continue;
			}
			else break;
		}
		for(i=0;i<btree->active_node->total_node_keys;i++){
			if(btree->active_key->right_node == bid)
				return (btree->active_key);
			if(IncrementPosition(btree)!=SUCCESS){
				Debug("Couldnt increment\n");
				return NULL;
			}
		}
		return NULL;
	}
	Rewind(btree);
	for(i=1; i < (hold_posn - 1); i++){
		if(IncrementPosition(btree)!=SUCCESS){
			Debug("Couldnt increment\n");
			return NULL;
		}
	}
	return (btree->active_key);
}

/*
// NAME:	CurrentKey
//
// DESCRIPTION:	Identify the current key.
//
// RETURN:	Returns a pointer to the key group which is designated 
//		as the active key
*/
struct KeyGroup *  CurrentKey(BTREE * btree /* pointer to tree descriptor */)
{

	Trace("CurrentKey(%x)\n", (unsigned)btree);
	if(btree->exhausted)
		return FAIL;
	if(btree->active_key == NULL) 
		return NULL;
	/* exhausted root node*/
	if ((btree->vector == 0) && ( btree->active_node->total_node_keys == 0 )){
		/* a root node can be fully exhausted*/
		return NULL;
        }
	else return (btree->active_key);
} /* CurrentKey*/

/*
// NAME:	Update
//
// DESCRIPTION:	Update the data of the current key
//
// RETURN:	Overwrites the key data or the address stored in a key
*/
int  Update(BTREE * btree /* pointer to tree descriptor */, 
	    void * new_data /* new key data, consistent in type to data being replaced */)
{

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

	if(btree->exhausted)
		return FAIL;
	if(btree->active_key == NULL) 
		return FAIL;
	mv_mem((char *)new_data, btree->active_key->KeyData.key_data,
			USRDATASIZE /* normally sizeof(long)*/ );
	(btree->hierarchy_list+btree->vector)->state = DIRTY;
	return SUCCESS;
} /* Update*/



/*
// NAME:	FlushHierarchy
//
// DESCRIPTION:	The hierarchy leading to a node is held in a vector of 
//		nodes beginning with the root node and ending with the
//		active node.  Nodes that have been modified are marked
//		in the hierarchy as "dirty".  When a new node is being
//		listed into the hierarchy, it may overlay a node already
//		listed in the node.  The underlying node is written back
//		to disk before the new node overwrites.  This function
//		walks the hierarchy, writes dirty nodes to disk and 
//		marking them clean.
//
// RETURN:	SUCCESS or FAIL
//
*/
int FlushHierarchy(BTREE * btree /* pointer to tree descriptor */)  
{
/* *** Although left as though it is completely empty, the loaded */
/* *** nodes are still there, and will be reused by load routines*/
/* *** later as required.*/
	int position, doexchange;
	long exchange_addr;
	long child;

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

	for(position = 0; position < btree->blocks_to_flush ; position++){
#ifdef COMPRESS
/* this routine will compress the tree into the lowest addressed blocks*/
		if( (position + 1) < btree->blocks_to_flush){
			child = (btree->hierarchy_list+(position+1))->block_id;
			/* look for the child*/
			if( ( btree->bfh->first_free_block_addr != -1L )&&
				( child > btree->bfh->first_free_block_addr)) {

		                OpenKeyNode(btree,&(btree->hierarchy_list+position)->hierarchy_node);
				doexchange = 0;
				if( btree->left == child ){
					exchange_addr = BfhNewBlock(btree->bfh);
					btree->active_node->nodeblock.left_node = exchange_addr;
					doexchange=1;
				}else{
					do{
					    if(btree->active_key->right_node == child){
						    exchange_addr = BfhNewBlock(btree->bfh);
					    	    btree->active_key->right_node = exchange_addr;
						    doexchange=1;
						    break;
					    }
					}while(IncrementPosition(btree)==SUCCESS);
				}
				if(doexchange){
					(btree->hierarchy_list+position)->state = DIRTY;
					BfhFreeBlock(btree->bfh,(btree->hierarchy_list+(position+1))->block_id);

					(btree->hierarchy_list+(position+1))->block_id = exchange_addr;
					(btree->hierarchy_list+(position+1))->state = DIRTY;
				}
			}
		}
#endif
		if((btree->hierarchy_list+position)->state == DIRTY){
                        if(BfhWriteBlock(btree->bfh, (char *)&((btree->hierarchy_list+position)->hierarchy_node),(btree->hierarchy_list+position)->block_id) == SUCCESS){
				(btree->hierarchy_list+position)->state = CLEAN;
			}
			else {