main.cc

为数据库创建索引的B+树的算法实现。功能包括创建删除节点、条目等。最终将树递归打印于屏幕。（包含内存资源管理）

#include "btree.h"
#include "pagemgr.h"

using namespace std;
#include <iostream>
#include <fstream>

int degree;	// only allow degree d>=1
int CACHE_SIZE;
int E_dnodes,E_inodes;
BTNode* E_PrevLeafNode;

void CheckNode(BTree* bt,BTNode* node,int minVal,int maxVal) {
	int KeyNum=node->getNumKey();
	
	// check key consistency
	for (int i=0;i<KeyNum-1;i++) {
		if (node->getKey(i)>=node->getKey(i+1)) 
			printf("key order inconsistency of block %d at level %d\n",
					node->block,node->level);
	}
	if (KeyNum>=1) {
		if (node->getKey(0)<minVal||node->getKey(KeyNum-1)>=maxVal)
			printf("key order inconsistency of block %d at level %d\n",
					node->block,node->level);
	}	
	
	if (node->isLeafNode()) {
		E_dnodes++;	
		if (node->getNumKey()<degree+1) {	// half full cond.	
			if (node!=bt->root)
				printf("Half full cond. of block %d violated\n",node->block);
		}		
		
		if (E_PrevLeafNode==NULL) 
			E_PrevLeafNode=node;
		else {	// check sibling pointer
			if (E_PrevLeafNode->getNextSib()!=node)
				printf("Sibling pointer of block %d violated\n",
				E_PrevLeafNode->block);
			E_PrevLeafNode=node;
		}		
	} else {
		E_inodes++;
		if (node->num_ptr<degree+1) {		// half full cond.	
			if ((node!=bt->root)||
				(node==bt->root&&node->num_ptr<2)) 
				printf("Half full cond. of block %d violated\n",node->block);
		}
		
		// recursive checking
		for (int i=0;i<node->num_ptr;i++) {
			int NminVal=(i==0)?minVal:node->getKey(i-1);
			int NmaxVal=(i==node->num_ptr-1)?maxVal:node->getKey(i);
			CheckNode(bt,node->getPtr(i),NminVal,NmaxVal);
		}
	}
}

void TreeDoctor(BTree* bt) {
	printf("Examining B+ tree ...\n");
	E_dnodes=E_inodes=0;	E_PrevLeafNode=NULL;
	CheckNode(bt,bt->root,INT_MIN,INT_MAX);
	if ((E_dnodes!=bt->dnodes)||(E_inodes!=bt->inodes)) 
		printf("required-d:%d, acutal-d:%d,required-i:%d, actual-i:%d,dnodes, inodes statistics inconsistency\n",E_dnodes,bt->dnodes,E_inodes,bt->inodes);
	if (E_dnodes+E_inodes+getNumBlockAvail()!=CACHE_SIZE)
		printf("Memory corrupted\n");
	printf("B+ tree examined\n");
}

void RandomInsertion(BTree* bt,int seed,int num) {
	int key,value;
	srand(seed);
	int succCnt=0;
	for (int i=0;i<num;i++) {		
		key=value=rand()%100000;
	//	printf(" insert %d\t",key);
		if (bt->insert(key,value)) {succCnt++;}
	}
	printf("%d out of %d insertion(s) succeed\n\n",succCnt,num);
}

void RandomDeletion(BTree* bt,int seed,int num) {
	srand(seed);
	int succCnt=0;
	for (int i=0;i<num;i++) {		
		int key=rand()%100000;
		if (bt->remove(key)) succCnt++;
	}
	printf("%d out of %d deletion(s) succeed\n\n",succCnt,num);
}

void printStat(BTree* bt) {
	printf("%d dnode(s), %d inode(s), %d free block(s)\n",
	bt->dnodes,bt->inodes,getNumBlockAvail());
}

void printCmdUsage() {
	printf("[Commands]\n");
	printf("i key value\n");
	printf("d key\n");
	printf("ri seed num (key same as value)\n");
	printf("rd seed num\n");
	printf("qp key\n");
	printf("qr minkey maxkey (inclusive)\n");
	printf("stat\n");
	printf("check\n");
	printf("prntree\n");
	printf("\n");
}

void ParseCommand(char* filename) {
	const int LINE_LEN=1024;
	char line[LINE_LEN];
	const char* delim=" ";
	
	int NumParam;
	int param[2];
	char *cmd,*tok;
	
	ifstream br(filename);
  	if (! br.is_open())
  	{ printf("Error opening file \"%s\"",filename); exit (1); }
  	
  	// do not check for error input !
  	BTree* bt = new BTree();
	while(br.getline(line,LINE_LEN)) {
		cmd=strtok(line,delim);		// class tag of the record
		if (cmd==NULL) continue;
		
		NumParam=0;
		while (NumParam<2&&(tok=strtok(NULL,delim))!=NULL) {        	
        	param[NumParam]=atoi(tok);
        	NumParam++;        	
        }
        
        bool validCmd=true;        
        if (NumParam==0) {
        	if (strcmp(cmd,"prntree")==0) {
				bt->printTree(); printf("\n");
			} else if (strcmp(cmd,"stat")==0) {
				printStat(bt); printf("\n");
			} else if (strcmp(cmd,"check")==0) {
				TreeDoctor(bt); printf("\n");
			} else validCmd=false;
        } else if (NumParam==1) {
        	if (strcmp(cmd,"d")==0) {
        		if (!bt->remove(param[0]))
        			printf("Cannot delete key %d\n\n",param[0]);
			} else if (strcmp(cmd,"qp")==0) {
				int _key=param[0],_value;				
				if (bt->find(_key,_value)) printf("Key value pair: (%d,%d)\n",_key,_value); 
				else printf("Key %d not found\n",_key);
				printf("\n");
			} else validCmd=false;
        } else if (NumParam==2) {
			if (strcmp(cmd,"ri")==0) {
				RandomInsertion(bt,param[0],param[1]);
			} else if (strcmp(cmd,"rd")==0) {
				RandomDeletion(bt,param[0],param[1]);
			} else if (strcmp(cmd,"i")==0) {
				if (!bt->insert(param[0],param[1]))
					printf("Cannot insert the entry (%d,%d)\n\n",param[0],param[1]);
			} else if (strcmp(cmd,"qr")==0) {
				printf("Range query result:\n");
				int num_rst=bt->printRange(param[0],param[1]); 
				printf("# of results: %d\n",num_rst);
				printf("\n");
			} else validCmd=false;
    	}
    	if (!validCmd) {
    		printf("Invalid command: '%s'",cmd);
    		for (int i=0;i<NumParam;i++) printf(" '%d'",param[i]);
    		printf("\n");
    		printCmdUsage();
    		break;
    	}
	}
	delete  bt;
	br.close();
}

int main(int argc, char *argv[]) {		

	// do not check arguments
	if (argc<2||argc>4) {
		printf("Usage: %s cmdfile [cachesize] [degree]\n",argv[0]);
		return 0;
	}
	char* filename=argv[1];	
	CACHE_SIZE=(argc>=3)?atoi(argv[2]):256;	// default cachesize: 256
	degree=(argc>=4)?atoi(argv[3]):2;		// default degree: 2	
		
	if (CACHE_SIZE<1) { printf("cachesize must be integer >=1\n");return 0;}
	if (degree<1) { printf("degree must be integer >=1\n");return 0;}
	
	// print paramters
	printf("filename: %s, cachesize: %d, degree: %d\n\n",
	filename,CACHE_SIZE,degree);
	
	InitByDegree(CACHE_SIZE,degree);	
	ParseCommand(filename);
	DestroyPagePool();
	getchar();
	return 0;
}