b+

/* BPlus Tree Project*//*  To Compile      g++ Bplustree.cpp -g -o Bplustree    *//*  To Run          ./Bplustree  <inputs>                *//*  By: Farah Khan*//*Project Description: This assignment is designed to learn how B++ trees are made, how to insert keys and theirvalues. The basic purpose of B+ Tree is to form indices to allow a fast and reliable search mechanism.When running the program user has to put if they want duplicates in their B+ tree and if the debug mode is one.Then the user has to input the keys and their values which will be stored in a file as a B+ Tree.*//*Input FormateRunning: ./Bplustree (filename) (1 - for duplicates, 0 - no duplicates) (1 - debug mode, 0 - no debug mode)insert(key, pointer)lookup(key)lookup(key1,key2)print treeexit*///Includes#include <stdio.h>#include <fcntl.h>#include <sys/stat.h>#include <string.h>#include <iostream>#include "Bplustree.h"//function that reads each block from the filestatic void ReadBlock(int File, int Block, int Size, void *Addr) {	if (DEBUG == 1)		{			cout <<"Read Block Function :- File:"<< File << " Block: " << Block;			cout << " Size: "  << Size << " Address: " << Addr << endl;		}	if(lseek(File, Block * Size, SEEK_SET) == -1 || read(File, Addr, Size) == -1)	{	   	cout <<"Read Block Error :- File:"<< File << " Block: " << Block;	   	cout << " Size: " << Size << endl;	}}// function that writes each block to the filestatic void WriteBlock(int File, int Block, int Size, void *Addr) {	if (DEBUG == 1)	{		cout <<"Write Block Function :- File:"<< File << " Block: " << Block;		cout << " Size: "  << Size << " Address: " << Addr << endl;	}	if(lseek(File, Block * Size, SEEK_SET) == -1 || write(File, Addr, Size) == -1)	{	   	cout <<"Write Block Error :- File:"<< File << " Block: " << Block;	   	cout << " Size: " << Size << endl;	}}//read head used only in the start of the program.static void ReadHead(int Index) {	HeadType HeadBlock;	ReadBlock(File(Index), 0, BLKSIZE, &HeadBlock);	Root(Index) = HeadBlock.RootBlock;	Alloc(Index) = HeadBlock.AllocBlock;}//write head used only in the start of the programstatic void WriteHead(int Index) {	HeadType HeadBlock;        int i;	HeadBlock.RootBlock = Root(Index);	HeadBlock.AllocBlock = Alloc(Index);	WriteBlock(File(Index), 0, BLKSIZE, &HeadBlock);}//This function opens a new tree file as binary and intializing arugments as specified by the user.// This function als makes sure if the file is going to be new or has it already been created.int OpenTree(char *Name, int DupKeys) {	if (DEBUG == 1)		cout<<"Open New Tree Function"<<endl;	int i;	int j;	for(i = 0; i < NIDX; i++)		if(!Used(i)) break;	Used(i) = 1;	strcpy(IdxTab[i].Name, Name);	Dups(i) = DupKeys;	CBlk(i) = -1;	if((File(i) = open(Name, O_RDWR|O_BINARY)) >= 0)	{		if (DEBUG == 1)			cout<<"Read File that is already created"<<endl;		ReadHead(i);	}	else/*	if((File(i) = creat(Name, S_IREAD|S_IWRITE)) >= 0) {    */        if((File(i) = open(Name, O_RDWR|O_CREAT|O_BINARY, 0644)) >= 0) {			if (DEBUG == 1)				cout<<"Open New File"<<endl;		TreeNode Node;		Root(i) = 1;		Alloc(i) = 2;		WriteHead(i);		Node.LeafNode = 1;		Node.KeyCount = 0;	        for(j = 0; j < FANOUT-1; j++)                  {                    Node.Ptrs[j] = -1;                    Node.Keys[j] = 0;                   }		Node.Ptrs[FANOUT - 1] = -1;		WriteBlock(File(i), 1, BLKSIZE, &Node);	} else {		perror("Error in opening file/creating file");		Used(i) = 0;		i = -1;	}	return i;}//Used at the end of the program to end the programvoid CloseTree(int Index) {	WriteHead(Index);	close(File(Index));	Used(Index) = 0;}//Function used to find the key, this function is called by the look up function.static int FindKey(TreeNode *Node, int Key) {	if (DEBUG == 1)	{		cout << "Find Key Function" << endl;		cout << "Node->KeyCount: " << Node->KeyCount << endl;	}	int k;	for(k = 0; k < Node->KeyCount; k++)	{		if(Node->Keys[k] > Key)		{			if (DEBUG == 1)					cout << "Node->Keys[k] > Key " << Node->Keys[k] <<  endl;			break;		}	if (DEBUG == 1)		cout << "Return Key Count: " << k <<  endl;	}	return k;}//check buckets is called when using duplicate indices. also used for look upstatic void CheckBucket(int Index, TreeNode *Node, int *Key, int *Ptr) {	if (DEBUG == 1)			cout << "Check Bucket Function " << endl;	*Ptr = -1;	if(CBlk(Index) >= 0) {		int NextPtr;	*Key = Node->Keys[CKey(Index)-1];	*Ptr = Node->Ptrs[CKey(Index)];	if(Dups(Index)) {/*		BucketType Bucket;   */		ReadBlock(File(Index), *Ptr, BLKSIZE, &Bucket);		if (DEBUG == 1)			cout << "Reading Block with pointer as bucket number: " << Node->Ptrs[CKey(Index)] << endl;		*Ptr = Bucket.Pointers[CPtr(Index)];		if (DEBUG == 1)			cout << "The New Pointer is: " << Bucket.Pointers[CPtr(Index)] << endl;		CPtr(Index)++;		NextPtr = Bucket.Pointers[CPtr(Index)];		if (DEBUG == 1)			cout << "Pointer to Next Bucket for Duplicates "<< NextPtr << endl;	}	if(!Dups(Index) || NextPtr < 0) {		CPtr(Index) = 0;		CKey(Index)++;		if(CKey(Index) > Node->KeyCount) {			CBlk(Index) = Node->Ptrs[0];			if (DEBUG == 1)				cout << "Not Duplicate or Next Pointer is < 0, Current Block is: "<< CBlk(Index) << endl;			CKey(Index) = 1;		}	}	}}//look up function that takes in the parameters to search for the key through the b+ treeint Lookup(int Index, int Key) {	if (DEBUG == 1)		cout << "Lookup Key Function"<< endl;	TreeNode Node;	int Ptr;	CBlk(Index) = Root(Index);	if (DEBUG == 1)			cout << "Root Block in Lookup is: "<< CBlk(Index) << endl;	for(;;)	{		ReadBlock(File(Index), CBlk(Index), BLKSIZE, &Node);		CKey(Index) = FindKey(&Node, Key);		if (DEBUG == 1)				cout << "The CKey Value is: " << CKey(Index) << endl;		if(Node.LeafNode)		{			if (DEBUG == 1)				cout << "Its a Leaf Node so break" << endl;			break;		}		CBlk(Index) = Node.Ptrs[CKey(Index)];		if (DEBUG == 1)			cout<<" The new Current CBLK Lookup: "<< CBlk(Index) <<endl;	}	CPtr(Index) = 0;	if(CKey(Index) == 0)		CBlk(Index) = -1;	CheckBucket(Index, &Node, &Key, &Ptr);	cout << "Pointer is: " << Ptr << endl;	return Ptr;}//The print function that prints out the whole tree according to its blocks and duplicate buckets.int print(int Index, char *filename) {		if (DEBUG == 1)			cout << "Print Function"<< endl;	TreeNode Node;	struct stat results;	if(stat(filename, &results) == 0)	{		if (DEBUG == 1)			cout << "Getting File Size to get Number of Blocks"<< endl;		FILE_SIZE = results.st_size;		TOTAL_BLOCKS = (FILE_SIZE - 40)/40;		if (DEBUG == 1)		{			cout<<"File Size: "<<FILE_SIZE<<endl;			cout<<"Total Blocks: "<<TOTAL_BLOCKS<<endl;		}	}	else		cout<<"Error Opening File"<<endl;    for(int i = 1; i <= TOTAL_BLOCKS; i++)    {		int k =0;		cout << "\nBlock Number: " << i<<"       ";		ReadBlock(File(Index), i, BLKSIZE, &Node);		if (DEBUG == 1)			cout << "Displaying Keys for non-leaf nodes"<< endl;		if(Node.KeyCount!=0 && !Node.LeafNode)		{			CKey(Index) = k;			cout << " pointer: " <<  Node.Ptrs[CKey(Index)];		}		else if(Node.KeyCount!=0 && Node.LeafNode)		{			CKey(Index) = k;			cout << " pointer: " <<  Node.Ptrs[CKey(Index) + 1];		}		if (DEBUG == 1)			cout << "Displaying keys and pointers for leaf nodes"<< endl;		if(Node.LeafNode)		{			for(k = 0; k < Node.KeyCount; k++)			{				CKey(Index) = k;				CBlk(Index) = Node.Ptrs[CKey(Index)+2];				if(Node.LeafNode)				{					//CBlk(Index) = -1;					if(k == (Node.KeyCount)-1)					{						CKey(Index) = 0;						cout << " Key: " << Node.Keys[k];						cout << " pointer: " <<  Node.Ptrs[CKey(Index)];					}					else					{						cout << " Key: " << Node.Keys[k];						cout << " pointer: " <<  CBlk(Index);					}				}			}		}		else if(!Node.LeafNode)		{			for(k = 0; k < Node.KeyCount; k++)			{				CKey(Index) = k;				CBlk(Index) = Node.Ptrs[CKey(Index)+1];					cout << " Key: " << Node.Keys[k];					cout << " pointer: " <<  CBlk(Index);				}		}		if (DEBUG == 1)			cout << "Checking for Duplicates for display"<< endl;   		 if(DUPLICATES == 1)   			{				int j = 0;				if(Node.LeafNode){					for(k = 0; k < Node.KeyCount; k++) {						CKey(Index) = k;						cout << "\nBucket: " << Node.Ptrs[CKey(Index) + 1]  << "        ";							ReadBlock(File(Index), Node.Ptrs[CKey(Index) + 1], BLKSIZE, &Bucket);							j=0;							while (Bucket.Pointers[j] != -1)							{								CPtr(Index) = j;								cout << "pointers:  " << Bucket.Pointers[CPtr(Index)] << "      ";								j++;							}				}			}  		}	} // end of for loop	cout << "\n";}//This function is used when inserting new keys and their pointers. It performers all the necessary// splits of the tree to make it balance and compli to the b+ tree algorithmstatic int InsertKey(int Index, TreeNode *Node, int KIdx, int *Key, int *Ptr) {	if (DEBUG == 1)			cout << "Insert Key Function"<< endl;	int Keys[FANOUT], Ptrs[FANOUT+1];	int Count, Count1, Count2, k;	Count = Node->KeyCount + 1;	Count1 = Count < FANOUT ? Count : FANOUT/2;	Count2 = Count - Count1;	for(k = FANOUT/2; k < KIdx; k++) {		Keys[k] = Node->Keys[k];		Ptrs[k+1] = Node->Ptrs[k+1];	}	Keys[KIdx] = *Key;	Ptrs[KIdx+1] = *Ptr;	for(k = KIdx; k < Node->KeyCount; k++) {		Keys[k+1] = Node->Keys[k];		Ptrs[k+2] = Node->Ptrs[k+1];	}	for(k = KIdx; k < Count1; k++) {		Node->Keys[k] = Keys[k];		Node->Ptrs[k+1] = Ptrs[k+1];	}	Node->KeyCount = Count1;	if(Count2) {		int s, d;		TreeNode NNode;		NNode.LeafNode = Node->LeafNode;		Count2 -= !Node->LeafNode;		for(s = FANOUT/2 + !Node->LeafNode, d = 0; d < Count2; s++, d++) {			NNode.Keys[d] = Keys[s];			NNode.Ptrs[d] = Ptrs[s];		}		NNode.Ptrs[d] = Ptrs[s];		NNode.KeyCount = Count2;		*Key = Keys[FANOUT/2];		*Ptr = Alloc(Index)++;		if(Node->LeafNode) {  /* insert in sequential linked list */			NNode.Ptrs[0] = Node->Ptrs[0];			Node->Ptrs[0] = *Ptr;		}		if (DEBUG == 1)			cout << "Write to Block Function where Block equals: " << *Ptr << endl;		WriteBlock(File(Index), *Ptr, BLKSIZE, &NNode);		WriteHead(Index);	}	return Count2;}//Used to creat new buckets when inserting duplicate keys.static int NewBucket(int Index, int Ptr, int Next) {	if (DEBUG == 1)		cout << "New Bucket Function " << endl;	int BBlk;        int j;	BucketType Bucket;	Bucket.Pointers[0] = Ptr;    Bucket.Pointers[1] = -1;	Bucket.NextBucket = Next;	Bucket.BucketId = BKTNUM + 1;	if (DEBUG == 1)		cout << "Bucket Id: " << Bucket.BucketId << endl;	BBlk = Alloc(Index)++;	WriteBlock(File(Index), BBlk, BLKSIZE, &Bucket);	WriteHead(Index);	return BBlk;}static int Error;//Record Insert, is called by the insert funciton to insert the key at the right place and to split the tree// if neededstatic int RecInsert(int Index, int Block, int *Key, int *Ptr) {	if (DEBUG == 1)	{		cout<<"RecInsert Function"<<endl;	    cout<<"Block from Insert: "<< Block<<endl;	}	TreeNode Node;	int KIdx, Split = 0;	int EqualKey;	ReadBlock(File(Index), Block, BLKSIZE, &Node);	KIdx = FindKey(&Node, *Key);	EqualKey = KIdx && Node.Keys[KIdx-1] == *Key;	if (DEBUG == 1)		cout << "The Key equals: " << EqualKey << endl;	if(!Node.LeafNode)	{		Split = RecInsert(Index, Node.Ptrs[KIdx], Key, Ptr);		if (DEBUG == 1)			cout << "Not the Leaf Node, Call Split recursively: " << Split << endl;	}	if(Split || Node.LeafNode && !EqualKey)	{		if(Node.LeafNode && Dups(Index))			*Ptr = NewBucket(Index, *Ptr, -1);		Split = InsertKey(Index, &Node, KIdx, Key, Ptr);		if (DEBUG == 1)			cout << "Leaf Node, Call Split from Insert Key: " << Split << endl;		WriteBlock(File(Index), Block, BLKSIZE, &Node);	}	else if(Node.LeafNode && Dups(Index))	{	 	if (DEBUG == 1)	    	cout << "Inserting when considering Duplicate Keys" << endl;		BucketType Bucket;		int i;		ReadBlock(File(Index), Node.Ptrs[KIdx], BLKSIZE, &Bucket);		for(i = 0; i < BKTPTRS && Bucket.Pointers[i] >= 0; i++);		if(i < BKTPTRS)		{		    Bucket.Pointers[i] = *Ptr;		    if(i < BKTPTRS-1) Bucket.Pointers[i+1] = -1;		    {				if (DEBUG == 1)					cout << "Write to Block Function where Block equals: " << Node.Ptrs[KIdx] << endl;		    	WriteBlock(File(Index), Node.Ptrs[KIdx], BLKSIZE, &Bucket);			}		}		else		{			cout << "ERROR: Bucket Overflow" << endl;		}	}	else if(Node.LeafNode)	{		Error = -1;	}	return Split;}//first function called by the insert operation that initiliazes everything and assigne the appropriate variablesint Insert(int Index, int Key, int Ptr) {	if (DEBUG == 1)		cout << "Entering Insert Function" << endl;	int Split;	Error = 0;	Split = RecInsert(Index, Root(Index), &Key, &Ptr);	if(Split) {		if (DEBUG == 1)			cout << "Create New Tree Node if Split is true:" << Split << endl;		TreeNode Node;		Node.LeafNode = 0;		Node.KeyCount = 1;		Node.Keys[0] = Key;		Node.Ptrs[1] = Ptr;		Node.Ptrs[0] = Root(Index);		Root(Index) = Alloc(Index)++;		if (DEBUG == 1)			cout << "Write to Block Function where Block equals: " << Root(Index) << endl;		WriteBlock(File(Index), Root(Index), BLKSIZE, &Node);		WriteHead(Index);	}	//cout<<"CBLK: "<< CBlk(Index)<<endl;	CBlk(Index) = -1;	//cout<<"CBLK: "<< CBlk(Index)<<endl;	return Error;}//function is called to print out all the keys and their pointers as specified by the rangevoid LookupRange(int Index, int key1, int key2, char *filename ){	    int j;		if (DEBUG == 1)			cout << "Get values for a Range of Keys:" << endl;		TreeNode Node;		struct stat results;		if(stat(filename, &results) == 0)		{			FILE_SIZE = results.st_size;			TOTAL_BLOCKS = (FILE_SIZE - 40)/40;			if (DEBUG == 1)			{				cout<<"Total Blocks: "<<TOTAL_BLOCKS<<endl;				cout<<"File Size: "<<FILE_SIZE<<endl;			}		}		else			cout<<"Error Opening File"<<endl;		for(int i = 1; i <= TOTAL_BLOCKS; i++)		{			ReadBlock(File(Index), i, BLKSIZE, &Node);			if(Node.LeafNode)			{				if (DUPLICATES == 1)				{					for (int k = 0; k < Node.KeyCount; k++)					{						if(Node.Keys[k] >= key1 && Node.Keys[k] <= key2 )						{							CKey(Index) = k;							cout << "\nKey: " << Node.Keys[k] << "  pointers:  ";							ReadBlock(File(Index), Node.Ptrs[CKey(Index) + 1], BLKSIZE, &Bucket);							j=0;							while (Bucket.Pointers[j] != -1)							{								CPtr(Index) = j;								cout << Bucket.Pointers[CPtr(Index)] << ", ";								j++;							}						}					}				}				else				{				 //cout << "Node.KeyCount " << Node.KeyCount					for (int k = 0; k < Node.KeyCount; k++)					{						if(Node.Keys[k] >= key1 && Node.Keys[k] <= key2 )						{							CKey(Index) = k;							cout << "\nKey: " << Node.Keys[k] << " Pointer: " << Node.Ptrs[CKey(Index) + 1];						}					}			    }			}		}		cout << "\n";	return;}//MAINint main(int argc, char *argv[]){	//varaible decleration	char inputToks[20][100];	char inputText[50];	char *token;	int inserted_key;	int lookup_key = 0;	int lookup_key2 = 0;	int data;	int  XEntryNum;	int RetnCode;	int XPtr;	int j;	char *filename = argv[1];	DUPLICATES  = atoi(argv[2]);	DEBUG = atoi(argv[3]);	if (DEBUG == 1)		cout << "Debug mode is on:" << endl;    XEntryNum = OpenTree(filename, DUPLICATES);	cout << "XEntryNum = " << XEntryNum << endl;	// while loop to get all the required information from the user and descarding unnessary characterss	do	{		if (DEBUG == 1)			cout << "Enter the command, Lookup or Insert" << endl;		cin.getline(inputText,1000);		token = strtok(inputText, " (,)");		int numToks = 0;		while(token != NULL)		{			strcpy(inputToks[numToks], token);			token = strtok(NULL, " (,)");			numToks++;		}		if(strcmp(strupr(inputToks[0]), "LOOKUP") == 0) // checking for look up and calling the functions		{			lookup_key2 = 0;			lookup_key = atoi(inputToks[1]);			lookup_key2 = atoi(inputToks[2]);			if(lookup_key2 != 0 )				LookupRange(XEntryNum,lookup_key,lookup_key2, filename);			else			{				XPtr = Lookup(XEntryNum, lookup_key);				// also print out single values for the first token.				if (DUPLICATES == 0)						 cout << "Key value is: " << lookup_key << " and Ptr value is: " << XPtr<< endl;				if (DUPLICATES == 1) {						 j = 0;						 while (Bucket.Pointers[j] != -1)  {							cout << "Ptr value is: " << Bucket.Pointers[j] << endl;							j++;						   }				}			}		}		else if (strcmp(strupr(inputToks[0]), "INSERT") == 0) // checking for insert and calling insert function		{			inserted_key = atoi(inputToks[1]);			data = atoi(inputToks[2]);			RetnCode = Insert(XEntryNum, inserted_key, data);			if (RetnCode != 0)              cout<<"Error During Key Insertion\n";		}		else if (strcmp(strupr(inputToks[0]), "EXIT") == 0) // to EXIT		{			cout << "Ending Program " << endl;			CloseTree(XEntryNum);		}		else if (strcmp(strupr(inputToks[0]), "PRINT") == 0 &&		strcmp(strupr(inputToks[1]), "TREE") == 0) // To PRINT TREE		{			//cout << "Print Tree " << endl;			print(XEntryNum,filename);		}		else		{			cout << "Unknown Command: Please Try Again" << endl;		}	} while(strcmp(strupr(inputToks[0]), "EXIT") != 0);return 0;}