btree.c

btree的实现源代码

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
                Larry A. Walker & Co. B+TreeR2
	Corp. 1991,1995 Larry A. Walker (Larry A. Walker & Co.)
	                All rights reserved.  
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

#include "treelib.h"
#include "btree.h"
#include "bfh.h"
#include "debug.h"

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
	standard compare routines
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/*
// NAME: 	pascal_string_compare
//
// DESCRIPTION:	The format of these strings consists of a leading byte 
//		which designates
//		the length of the string, followed by the contents of the 
//		string.
//		All comparison value routines must return -1, 0 or 1 as
//		the result of the comparison.  Note:  The specifications for
//		strncmp() do not meet this requirement.
//		Here, if the length of one string is less
//		than the length of another, it is automatically a value
//		less than aother.
//
// RETURN:	-1 LT, 0 EQ, 1 GT
//
*/
static int pascal_string_compare(union Key * value, /* A raw key */
			  struct KeyGroup * active_key,/* An encapsolated key */
			  int lng /* A place holder here */)
{
	int status;

	Trace("pascal_string_compare(%x, %x, %d)", (unsigned)value, (unsigned)active_key, lng);
	status = strncmp((value->key)+1,(active_key->k.key)+1,
		(active_key->k.key[0] > value->key[0])?
			(int)active_key->k.key[0]:value->key[0] );
	if(status==0)
		return status;
	return ( (status < 1)? -1 : 1 );
}

/*
// NAME:	long_compare
//
// DESCRIPTION:	Compare two long values, returning the result
//
// RETURN:	-1 LT, 0 EQ, 1 GT
//
*/
static int long_compare( union Key * value, /* A raw key */
		  struct KeyGroup * active_key, /* An encapsolated key */
		  int lng /* A place holder here */)
{
	Trace("long_compare(%x, %x, %d)", (unsigned)value, (unsigned)active_key, lng);
	if(value->long_key < active_key->k.long_key)
		return -1;
	if(value->long_key > active_key->k.long_key)
		return 1;
	return 0;
}

/*
// NAME:	double_compare
//
// DESCRIPTION:	Compare two double values, returning the result.  
	    It is possible for an archatecture to be satisified with a 32bit
	    alignment and complain when a double lands on a non 64 bit 
	    boundry - usually indicating a 64 bit fpu.  If everything else 
	    works fine except float trees, define _64BITFPU
	    example HP9000
//
// RETURN:	-1 LT, 0 EQ, 1 GT
//
*/
static int double_compare( union Key * value, /* A raw key */
		  struct KeyGroup * active_key, /* An encapsolated key */
		  int lng /* A place holder here */)
{
#ifdef _64BITFPU
	double vd, ad;
#else
#define vd value->double_key
#define ad active_key->k.double_key
#endif
	Trace("double_compare(%x, %x, %d)\n", (unsigned)value, (unsigned)active_key, lng);

#ifdef _64BITFPU
	memcpy((void *)&vd, (void*)&(value->double_key), sizeof(double));
	memcpy((void *)&ad, (void*)&(active_key->k.double_key), sizeof(double));
#endif
	if(vd < ad)
		return -1;
	if(vd > ad)
		return 1;
	return 0;
}

/*
// NAME:	fix_lng_compare
//
// DESCRIPTION:	Compare two fixed length values, returning the result.
//
// RETURN:	-1 LT, 0 EQ, 1 GT
//
*/
static int fix_lng_compare( 	union Key * value, /* A raw key */
			struct KeyGroup * active_key, /* An encapsolated key*/
			int lng /* key size */ )
{
	int status;

	Trace("fix_lng_compare(%x, %x, %d)", (unsigned)value, (unsigned)active_key, lng);
	status = strncmp(value->key,active_key->k.key,lng);
	if(status==0)
		return status;
	return ( (status < 1)? -1 : 1 );
}

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
	move memory
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */


/* 

//
// NAME:	move memory, allowing for overlapping memory areas
//
// DESCRIPTION:	Slower than any assembly language counterpart that 
//		would replace it, but this routine has proven most
//		trustworthy in any situation.
//
// RETURN:	NONE
//
*/
void mv_mem(	char *source,/* memory at */
		char *destin,/* memory to */
		int len /* for length */ )
{
	Trace("mv_mem(%x, %x, %d)\n", (unsigned)source, (unsigned)destin, len);
	if(len < 1)return;
	if(destin < source)
	{
		while(len--)
		{
			*destin=(*source); destin++; source++;
		}
		return;
	}
	else
	{
		source+=(len-1); destin+=(len-1);
		while(len--)
		{
			*destin=(*source); destin--; source--;
		}
		return;
	}
}

/* 
	--- Here is the alternative, if it works correctly, use it, the routine 
	    since the routine would be in assembly
*/

#define mv_mem(s,d,l) memmove(d,s,l)

/*
// NAME:	create_index_string
//
// DESCRIPTION:	This utility will take a null terminated C string and create
//		a pascal type string as required for indexing.  The first 
//		byte of the string provides the length of the string.  The
//		length of the string is therefor limited to 255 characters.
//		In actual indexing practice the it isnt reasonable to assume
//		that variable length keys should be allowed to be more than
//		about 64 characters.  
//		If you want your index to fail, change the commented code.
//		As it is, it will simply take the first MASVARSTR characters
//		from the string to create the index key string.
//
// RETURN:	SUCCESS or FAIL
//
*/

int create_index_string(char * to /*place the results here*/, 
			char * fm /*convert this string */)
{
	int i;

	Trace("create_index_string(%x,%x)\n", (unsigned)to, (unsigned)fm);

	i  = strlen(fm);

	if(i > MAXVARSTR){
		/*fprintf(stderr,"Warning: %s: Line %d: String too long",__FILE__, __LINE__);*/
		/*return FAIL;*/
		i=MAXVARSTR;
	}
	*to = (char)i;
	mv_mem(fm,to+1,i);
	return SUCCESS;
}

/*
// NAME:	create_c_string
//
// DESCRIPTION:	This utility will take an index type (pascal type) string 
//		and create a standard null terminated C string.
//
// RETURN:	Always returns SUCCESS
//
*/
int create_c_string(char * to /* put the new string here */, 
		    char * fm /* get the pascal string from here */) 
{
	int i;

	Trace(" create_c_string(%x,%x)\n", (unsigned)to, (unsigned)fm);

	i = (int)(*fm);

	strncpy(to,++fm,i);
	*(to+i) = 0;
	return SUCCESS;
}

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
	Btree class routines
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

/*
// NAME:	OpenKeyNode
//
// DESCRIPTION:	This function takes a pointer to a node and initializes
//		the class instance to use it as the current active node.
//		All active operations will be performed on this node.
//
// RETURN:	NONE
//
*/
void OpenKeyNode(BTREE * btree, /* tree descriptor pointer */
		 struct Node * n /* pointer to new active node */  )
{

	Trace("OpenKeyNode(%x,%x)\n", (unsigned)btree,
		(unsigned)n);
	btree->active_node = n;
	btree->left = btree->active_node->nodeblock.left_node;
	btree->key_position = 1;
	btree->active_key = (struct KeyGroup *)(((char *)n) + FirstKeyOffset); 
}

/*
// NAME:	Btree
//
// DESCRIPTION:	Btree initialization function.  Will create a new index if
//		second parameter is CREATE and index does not already exist.
//		The first parameter is the name of the index.
//		The third parameter is the type of key.
//		If the fourth parameter is set to 1, duplicate keys will be
//		allowed.  If 0 duplicates will not be allowed.
//		If the keys are not variable length, the fixed key length
//		size should be the fifth parameter.  For example, long keys
//		would be sizeof(long).
//
// RETURN:
//
*/
BTREE * OpenBtree(	char *index_name, /* disk file name */
			int create, /* true or false */
			int tok, /* VAR_LNG_KEY or FIX_LNG_KEY or LONG_KEY or DOUBLE_KEY */
			int dups, /* duplicate keys allowed, true or false */
			int fix_key_size /* ignored, or size of key if fixed length */)
{
	int i;
	BTREE * btree;

	Trace("OpenBtree( %s,%d,%d,%d,%d)\n", index_name, create, tok, 
		dups, fix_key_size);

	btree = (BTREE*)calloc( 1, sizeof(BTREE) );
	if(btree == NULL){
		Debug("Can't allocate space\n");
		return NULL;
	};
	
/*
*	--- Initialize the btree handle
*/
        btree->vector = -1;  /* -1 = empty*/
	btree->blocks_to_flush = 0;
	btree->ActiveHeight = 0;
	btree->hierarchy_list = NULL;
	btree->active_node = NULL;
	btree->active_key = NULL;
	btree->key_copy = NULL;
	btree->key_position = -1;
	btree->left = -1L;
	btree->past_exact_key = 0;
	btree->compare_funct = NULL;
	btree->rootsplit=0;
	btree->lock_on=0;

	if(create == CREATE ){
		btree->magic = 2216L;
		btree->search_levels = 0;
		btree->duplicates = dups;
		btree->type_of_key = tok;
		btree->fix_lng_key_lng = fix_key_size;
		btree->rootnode = 0L;
		btree->number_of_keys = 0L;
		btree->exhausted = 1;
		/*this will not be the same size as the bfh block_size*/
		btree->block_size = TreeBlockSize;
		/* override the lng parameter */
		switch(tok){
			case VAR_LNG_KEY:
				btree->fix_lng_key_lng = -1;
				break;
			case LONG_KEY:
				btree->fix_lng_key_lng = sizeof(long);
				break;
			case DOUBLE_KEY:
				btree->fix_lng_key_lng = sizeof(double);
				break;
			case FIX_LNG_KEY:
/*
*	--- Fix alignment problems on certain hardware (Sun)
*/
				if(fix_key_size)
#ifdef ALIGN2
				if(!((fix_key_size + 2 ) % 2) )
                                	btree->fix_lng_key_lng = fix_key_size;
				else
                                	btree->fix_lng_key_lng = fix_key_size +
                                	( 2 - ( (fix_key_size+2) % 2 ) );
#endif
#ifdef ALIGN4
				if(!((fix_key_size + 4 ) % 4) )
                                	btree->fix_lng_key_lng = fix_key_size;
				else
                                	btree->fix_lng_key_lng = fix_key_size +
                                	( 4 - ( (fix_key_size+4) % 4 ) );
#endif
				break;
			default:
				Debug("Invalid type of key\n");
				break;
		}
		if((btree->fix_lng_key_lng < 1) && (tok != VAR_LNG_KEY) ){
			Debug("Invalid key size\n");
			free ((void*)btree);
			return NULL;
		}
		btree->bfh = BfhOpen ( index_name, btree, sizeof(BTREE), CREATE, TreeBlockSize );
		if(btree == NULL){
			Debug("Failed to open %s\n", index_name);
			free ((void*)btree);
			return NULL;
		}
	}else{
		btree->bfh = BfhOpen ( index_name, btree, sizeof(BTREE), 0, 0);
		if(btree == NULL){
			Debug("Failed to open %s\n", index_name);
			free ((void*)btree);
			return NULL;
		}
		if(btree->magic != 2216L){
			Debug("%s Not a btree file\n",index_name);
			free ((void*)btree);
			return NULL;
		}
	}
	/* Next we need a hierarchy to store our nodes*/
	btree->ActiveHeight=(MaxHierarchyPointers >= 
		(btree->search_levels+2))?
		MaxHierarchyPointers:btree->search_levels+2;
	btree->hierarchy_list = (struct HierarchyBlock *)
		calloc(btree->ActiveHeight,sizeof(struct HierarchyBlock) );
	if(btree->hierarchy_list == NULL){
		Debug("Failed to allocate memory.\n");
		free( (void*)btree) ;
		return NULL;
	}
	for(i=0;i<btree->ActiveHeight;i++){
		(btree->hierarchy_list+i)->block_id = -1L;
		(btree->hierarchy_list+i)->state = CLEAN;
	}
	/* Install the comparison routine*/
	if(create != CREATE){
		if( (tok != btree->type_of_key) && (tok != 0) ){
			Debug("Invalid type of key\n");
		}
		tok = btree->type_of_key;
	}
	Trace("install tok # %d\n",tok);
	switch(tok){
		case VAR_LNG_KEY:
			btree->compare_funct = pascal_string_compare;
			break;
		case LONG_KEY:
			btree->compare_funct = long_compare;
			break;
		case DOUBLE_KEY:
			btree->compare_funct = double_compare;
			break;
		case FIX_LNG_KEY:
			btree->compare_funct = fix_lng_compare;
			break;
		default:
			Debug("Invalid type of key\n");
			break;
	}
	btree->time_of_last_open = time(NULL);
	return btree;
} /* Btree*/

/*
// NAME:	Close
//
// DESCRIPTION:	Shutdown a btree.
//
// RETURN:	Result of the block file handler closing function
//
*/
int Close(BTREE * btree /* pointer to tree descriptor */)
{
	int stat;

	Trace("Close(%x)\n", (unsigned)btree);
	FlushHierarchy(btree);
	free ((void *)btree->hierarchy_list);
	if(btree->key_copy != NULL)