btree.c

btree的实现源代码

		free((void *)btree->key_copy);
	btree->time_of_last_close = time(NULL);
	stat = -1;
	if(btree->bfh != NULL){
		stat = BfhClose( btree->bfh, btree, sizeof(BTREE) );
		if(!stat){
			Debug("Error in closing file\n");
		}
	}
	btree->bfh == NULL;
	return stat;
}

/*
// NAME:	InstallCompare
//
// DESCRIPTION:	Installs a new compare function for fixed length keys -
//		composite keys
//
// RETURN:	SUCCESS or FAIL
//
*/
int InstallCompare(BTREE * btree /* pointer to tree descriptor */, int (* fn)(union Key *, struct KeyGroup *, int) )
{
	Trace("InstallCompare(%x,%x)\n", (unsigned)btree, (unsigned)fn);

	if(btree->type_of_key == FIX_LNG_KEY){
		btree->compare_funct = fn;
		return SUCCESS;
	}
	return FAIL;
}

/*
// NAME:	Locate
//
// DESCRIPTION:	Provides public access to the private LocateExact function.
//
// RETURN:	result of the LocateExact function.
//
*/
int Locate(BTREE * btree /* pointer to tree descriptor */,
	   union Key * search_key /* A raw key */)
{

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

	if(btree->exhausted)
		return FAIL;
	/* access from outside, -1 level indicate search continues to leaf*/
	return LocateExact(btree, search_key);
}

/*
// NAME:	LocateInsert
//
// DESCRIPTION:	Search for an insert position at a specified level.
//		Called by the Insert function.
//
// RETURN:	SUCCESS, FAIL, NODE_EOF, or NEAR_MATCH
//
*/
static int LocateInsert(BTREE * btree /* pointer to tree descriptor */,
		 union Key * search_key /* An encapsolated key */,
		 int level /* specified level */)
{
	long next_node;
	int status,pos_status;

	Trace("LocateInsert(%x,%x,%d)\n",
		(unsigned)btree, (unsigned)search_key, level);

	next_node = btree->rootnode; /* root node */
	btree->vector = -1;
	btree->past_exact_key = 0;
	while(1){
		/* also opens the node*/
		if(LoadHierarchyNode(btree, next_node ) == FAIL){ 
			Debug("Cant load node\n");
			return FAIL;
		}
		if(btree->active_node->total_node_keys < 1){
			/* A tree deleted down to 0 keys*/
			if(next_node == btree->rootnode){
				return SUCCESS;
			}
			Debug("Empty node\n");
			return FAIL;
		}
		/* if the first key is already > the search key*/
		if(Compare(btree,search_key) == -1){
			if((level == btree->vector)||(btree->left == -1L)){
				return NEAR_MATCH;
			}
			next_node = btree->left;
			continue; 
		}
		/* walk forward until the key found or the search is > the*/
		/* found key*/
		while((pos_status = IncrementPosition(btree)) == SUCCESS){
			status = Compare(btree,search_key);
			if(status == -1 )
				break;
			if(status == 0 )
				btree->past_exact_key = 1;
			/* we must now not be past the position we would*/
			/* find the key, or at an insert position*/
		}
		/* if we couldnt increment*/
		if(pos_status == FAIL) 
			return FAIL;
		/* if we did increment*/
		if(pos_status == SUCCESS){
			/* status must be -1*/
			if((level == btree->vector)||(btree->left == -1L))
				return NEAR_MATCH;
			next_node = btree->left;
			continue;
		}
		if(pos_status == NODE_EOF){
			if((level == btree->vector) || (btree->left == -1L))
				return NODE_EOF;
			next_node = btree->left;
			continue;
		}
	}
} /* LocateInsert*/

/*
// NAME:	LocateExact
//
// DESCRIPTION: 	We are searching for an exact match at all levels.
//
// RETURN:	SUCCESS or FAIL
//
*/
static int LocateExact(BTREE * btree /* pointer to tree descriptor */,
	        union Key * search_key /* An encapsolated key */)
{
	long next_node;
	int status,pos_status;
	
	Trace("LocateExact(%x,%x)\n", (unsigned)btree, (unsigned)search_key);

	if(btree->exhausted)
		return FAIL;
	next_node = btree->rootnode; /* root node */
	btree->vector = -1;
	while(1){
		/* also opens the node*/
		if(LoadHierarchyNode(btree, next_node ) == FAIL){ 
			Debug("Cant load node\n");
			return FAIL;
		}
		if(btree->active_node->total_node_keys < 1){
			Debug("Empty node\n");
			return FAIL;
		}
		/* walk forward until the key found or the search is > the*/
		/* found key*/
		pos_status = SUCCESS;
		do {
			if((status = Compare(btree,search_key)) == 0 ){
				return SUCCESS;
			}
			if(status == -1 )
				break;
			/* we must now not be past the position we would*/
			/* find the key, or at an insert position*/
		} while((pos_status = IncrementPosition(btree)) == SUCCESS);
		/* if we couldnt increment*/
		if(pos_status == FAIL) 
			return FAIL;
		/* if we did increment*/
		if((pos_status == SUCCESS)||(pos_status == NODE_EOF)){
			/* status must be -1*/
			if(btree->left == -1L)
				return FAIL; /* couldnt find exact*/
			next_node = btree->left;
			continue;
		}
	}
} /* LocateExact*/

/*
// NAME:	InsertKey
//
// DESCRIPTION:	Insert a key into the tree, provide the key as a pointer
//		to a completed KeyGroup structure.
//
// RETURN:	SUCCESS or FAIL
//
*/
int InsertKey ( BTREE * btree /* pointer to tree descriptor */,
		struct KeyGroup * insert_group /* An encapsolated key */)
{
	/* outside access to the insert function*/
	int stat;

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

	btree->rootsplit = 0;
	insert_group->right_node = -1L; /* outside concerns cannot use a right*/
					/* node address*/
	stat = Insert(btree,insert_group, -1);  /* normal insert a leaf level*/
	if(stat == SUCCESS){
		btree->number_of_keys++;
		if(btree->exhausted)
			btree->exhausted = 0;
	}
		
	return stat;
} /* operator += */
	

/*
// NAME:	Insert
//
// DESCRIPTION:	Insert a new key, contained in pointed to key group, into
//		the tree at specified level
//
// RETURN:	SUCCESS or FAIL
//
*/
static int Insert(BTREE * btree /* pointer to tree descriptor */,
	   struct KeyGroup * insert_group /* An encapsolaed key */,
	   int level /* specified level for insert */)
{
	char *ptr;
	int i,status,half_posn;
	struct Node spare_node;
	struct KeyGroup nkey;
	long save_ptr;

	Trace("Insert(%x,%x,%d)\n", 
		(unsigned)btree, (unsigned)insert_group, level);
	if(btree->exhausted){ /* first key in tree*/
		ptr = (char *)&spare_node;
		for(i=0;i<sizeof(struct Node);i++)*ptr++=0;
		btree->active_node = &spare_node;
		btree->key_position = 1;
		btree->active_key = (struct KeyGroup *)(((char *)&spare_node) + FirstKeyOffset); 
		btree->active_node->total_node_keys = 0;
		btree->active_node->nodeblock.left_node = -1L;
		btree->left = btree->active_node->nodeblock.left_node;
		btree->active_node->next_free_position = FirstKeyOffset;
		status = InsertNodeKeyGroup(btree,insert_group);
		if (status == FAIL){
			Debug("Couldnt insert\n");
			return FAIL;
			}
		btree->rootnode = BfhNewBlock(btree->bfh);
		if(btree->rootnode == -1L){
			Debug("Couldnt get new block\n");
			return FAIL;
		}
	        if(BfhWriteBlock(btree->bfh,(char*)btree->active_node,btree->rootnode) == FAIL){
			Debug("Cant write block\n");
			return FAIL;
			}
		btree->search_levels = 1;
		LoadHierarchyNode(btree,btree->rootnode);
		return SUCCESS;
	}
        if( (level != -1 ) && (btree->rootsplit) ){
                /* If the root was split, all recursive inserts pending are*/
                /* off by one*/
                level++;
        }

	status = LocateInsert(btree, (union Key *)insert_group->k.key ,level);

	/* we could have eof success fail or near match */
	if(status == FAIL){
		Debug("Cant locate for insert\n");
		return FAIL;
	}
	if((status == SUCCESS)||(btree->past_exact_key) ){
		if(btree->duplicates == 0){
			Debug("No Duplicates Allowed\n");
			return FAIL;
		}
	}
	/* can also be NEAR_MATCH or NODE_EOF*/

	/* then must be near match or success with dups allowed or node eof*/
	status = InsertNodeKeyGroup(btree,insert_group);
	if(status == SUCCESS){
		return SUCCESS;
	}
	/* runtime_error(TRACE,__FILE__,__LINE__,"Node full");*/
	/* the only failure here is lack of space*/
	/* SPLIT the NODE*/
	/* if root node, make a new root node*/
	/* split out the left half to the spare node*/
	if(btree->vector < 0) {
		Debug("No node to split\n");
		return FAIL;
		}
	Rewind(btree);
	if(( btree->active_node->total_node_keys < 5 ) ||
		(half_posn = ( btree->active_node->total_node_keys / 2 )) 
		< SPLITKEYMIN){
		return FAIL;
		}
	ptr = (char *)&spare_node;
	for(i=0;i<sizeof(struct Node);i++)*ptr++=0;
/* HERE 0 or -1 ?? */
	spare_node.total_node_keys = 0;
	spare_node.nodeblock.left_node = -1L;
	spare_node.next_free_position = FirstKeyOffset;
	if(btree->vector == 0){
		for(i = 0; i < btree->active_node->total_node_keys/2; i++){
			if((status = InsertSpareKeyGroup(btree,btree->active_key,&spare_node))
				 == FAIL ){
				Debug("Failed to insert\n");
				return FAIL;
			}
			if( (status = DeleteNodeKeyGroup(btree)) == FAIL ){
				Debug("Key loss deleting during split\n");
			}
		}
		spare_node.nodeblock.left_node = btree->active_node->nodeblock.left_node;
		/* if root node move out the right half to another node*/
		/* leaving center key as root node*/
		btree->active_node->nodeblock.left_node = BfhNewBlock(btree->bfh);
		BfhWriteBlock(btree->bfh, (char *)&spare_node , btree->active_node->nodeblock.left_node );
		ptr = (char *)&spare_node;
		for(i=0;i<sizeof(struct Node);i++)*ptr++=0;
		spare_node.total_node_keys = 0;
		spare_node.next_free_position = FirstKeyOffset;
		if(btree->active_key->right_node != -1L){
			spare_node.nodeblock.left_node = btree->active_key->right_node;
		}
		else 
			spare_node.nodeblock.left_node = -1L;
		btree->active_key->right_node = BfhNewBlock(btree->bfh);
		/* bypass the center key as new single root key*/
		if(IncrementPosition(btree) != SUCCESS){
			Debug("failed to increment\n");
		}
		while(btree->key_position <= btree->active_node->total_node_keys){
			if((status = InsertSpareKeyGroup(btree,btree->active_key,&spare_node))
				 == FAIL ){
				Debug("Failed to Insert\n");
				return FAIL;
			}
			if( (status = DeleteNodeKeyGroup(btree)) == FAIL ){
				Debug("Key loss deleting during split\n");
			}
		}
		Rewind(btree);
		if ( BfhWriteBlock(btree->bfh, (char *)&spare_node , btree->active_key->right_node )
			== SUCCESS){
			FlushHierarchy(btree);
		        btree->search_levels ++;
		}
		/*021194 mark the global marker for root haveing been split */
		/*if(level != -1)	// if not insert in leaf*/
		/*	level++;	// we added a level*/
		btree->rootsplit = 1;
	} else	{
		int pos_status;

		for ( i = 0; i < half_posn; i++) {
			/* pick the middle key*/
			if(IncrementPosition(btree) != SUCCESS){
				Debug("failed to increment\n");
			}
		}
		if(btree->active_key->right_node != -1L){
			spare_node.nodeblock.left_node = btree->active_key->right_node;
		}
		else spare_node.nodeblock.left_node = -1L;
		save_ptr = BfhNewBlock(btree->bfh);
		btree->active_key->right_node = save_ptr;
		/* this key goes to the parent, and the rest of the*/
		/* node goes to the spare block*/
		/* struct KeyGroup * nkey = (struct KeyGroup *)calloc(1,sizeof(struct KeyGroup));*/
		mv_mem((char *)btree->active_key, (char *)&nkey, 
			KeyGroupSize(btree,btree->active_key));
		if( DeleteNodeKeyGroup(btree) == FAIL ){
			Debug("Key loss deleting during split\n");
		}
		while(btree->key_position <= btree->active_node->total_node_keys){
			if((status = InsertSpareKeyGroup(btree,btree->active_key,&spare_node))
				 == FAIL ){
				Debug("Failed to Insert\n");
				return FAIL;
			}
			if( DeleteNodeKeyGroup(btree) == FAIL ){
				Debug("Key loss deleting during split\n");
			}
		}
		BfhWriteBlock(btree->bfh, (char *)&spare_node , save_ptr );
		/* check the levels*/
/*if((btree->vector+1) >= btree->search_levels){*/
/*btree->search_levels = ( ( btree->vector + 1 would match search levels ) + 1 /* the new level );*/
/*		}*/

		/* we have a dangling nkey here*/
		if(Parent(btree) == NULL){
			Debug("Cant find parent\n");
		}
		if(btree->active_node->total_node_keys < 1){
			Debug("Empty node\n");
			return FAIL;
		}
		if(Compare( btree,(union Key *)nkey.k.key) != -1 ){
			while((pos_status = IncrementPosition(btree)) == SUCCESS){
				if((status = Compare(btree,(union Key *)nkey.k.key))
					 != 1 )
					break;
			}
			if(pos_status == FAIL){
				Debug("Couldnt increment\n");
				return FAIL;
			}
		}
		status = InsertNodeKeyGroup(btree,&nkey);
		if(status != SUCCESS){
			status = Insert(btree,&nkey,btree->vector); /* reload for this key*/
			}
		if(status == FAIL){
			Debug("Couldnt insert\n");
			return FAIL;
		}
	}
	/* we had to split it, so try it again*/
	FlushHierarchy(btree);
	return Insert(btree,insert_group, level);
} /* Insert*/

/*
// NAME:	DeleteKey
//
// DESCRIPTION:	Delete a key, pointed to by a union Key pointer.
//