//Filename: btree.h //Developer: Jay Suttiruttana #ifndef _BTREE_H_ #define _BTREE_H_ /* ** ** PURPOSE: To understand the file structure, and practice on implementing ** the Load data list, List, Show, Find, Add,Delete and Modify ** parts functions. ** ** DESCRIPTION: This is the specification file for the data structure and the ** helper functions used to program the Load, List, Show, Find, Add ** Delete, and Modify parts functions. ** *******************************************************************************/ #include //#include #include #include #include #include #include #define TRUE 1 #define FALSE 0 #define BUFFSIZE 512 #define FIELD1_SIZE 7 #define FIELD2_SIZE 10 #define FIELD3_SIZE 13 #define FIELD4_SIZE 7 #define FIELD5_SIZE 12 #define FIELD6_SIZE 16 #define FIELD7_SIZE 14 #define MAXKEYS 4 #define MINKEYS MAXKEYS/2 #define NIL (-1) #define NOKEY -1 #define YES 1 #define NO 0 typedef enum {NOT_FOUND, FOUND, NO_PROMOTION, PROMOTION, NO_DEMOTION, DEMOTION, ERROR} Status_type; typedef struct { int key; int rec_rrn; } Item_type; typedef struct { char RYOM [FIELD1_SIZE]; char FANNA [FIELD2_SIZE]; char PINCHERLE [FIELD3_SIZE]; char RICORDI [FIELD4_SIZE]; char TYPE [FIELD5_SIZE]; char MUS_KEY [FIELD6_SIZE]; char OPUS_NUMBER[FIELD7_SIZE]; } Record_type; typedef struct { Item_type item[MAXKEYS]; int keycount; int child[MAXKEYS+1]; } page_type; #define RECORDSIZE sizeof(Record_type) #define PAGESIZE sizeof(page_type) typedef struct { int root; int avail_list; int data_avail_list; int total_rec; } BHeader_type; typedef struct { int next; } AvlRec_type; int fd_indexfile, fd_datafile, fd_inputfile; /******************************************************************************/ void btclose(void); void btopen(void); int btread(int rrn, page_type *page_ptr); int btsearch(int, int, int *, int *); int btwrite(int rrn, page_type *page_ptr); Status_type btdelete(int key, page_type *parent, int parent_rrn, int parent_pos); int create_root(Item_type item, int left, int right); int create_tree( Record_type *); void dta_close(void); void dta_creat(void); void dta_open(void); void inp_close(void); void inp_open(char *filename); /******************************************************************************/ int Concatenate(page_type *page, page_type *parent, int parent_pos, page_type *sibling, int *sibling_rrn); void Concat_Right(page_type *page, page_type *parent, page_type *sibling, int parent_pos); void Concat_Left(page_type *page, page_type *parent, page_type *sibling, int parent_pos); void delete_rec(int rrn); void Display(Record_type record); int Enquire(char *s); void Error(char *s); void FreePage(int avail_rrn); int GetBtrAvlLst(void); void GetBtrAvlRec(int avail_rrn, int *next_avail_rrn); int GetDtaAvlLst(void); void GetDtaAvlRec(int avail_rrn, int *next_avail_rrn); int GetField(char [], char , int); int getpage(void); int GetRec(Record_type *record); int getroot(void); int get_rrn(void); Status_type insert(page_type *parent, int parent_rrn, int pos, Item_type item, int *promo_r_child, Item_type *promo_item); void ins_in_page(Item_type item, int r_child, page_type *p_page); void pageinit(page_type *p_page); void PutBtrAvlLst(int avail_rrn); void PutBtrAvlRec(int rrn, int next_avail_rrn); void PutDtaAvlLst(int avail_rrn); void save_record(int rec_rrn, Record_type record); void putroot(int root); void Rd_Right_Ins(page_type *sibling, page_type *parent, page_type *page, Item_type item, int r_child, int pos); void Rd_Left_Ins(page_type *sibling, page_type *parent, page_type *page, Item_type item, int r_child, int pos); Record_type RetrievRec(int rrn); int search_node(int key, page_type *p_page, int *pos); void split(Item_type item, int r_child, page_type *p_oldpage, Item_type *promo_item, int *promo_child, page_type *p_newpage); void Swap(page_type *page, int pos, page_type *leaf, int *leaf_rrn); int ShowTree(int rrn); void ShowPage(page_type *p_page); int Rdstrbt_Del(page_type *page, page_type *parent, int parent_pos, page_type *sibling, int *sibling_rrn); void Rd_Right_Del(page_type *sibling, page_type *parent, page_type *page, int parent_pos); void Rd_Left_Del(page_type *sibling, page_type *parent, page_type *page, int parent_pos); int Rdstrbt_Ins(Item_type item, int r_child, page_type *page, page_type *parent, int pos, page_type *sibling, int parent_rrn, int *sibling_rrn); int get_record( Record_type *record ); int getfield(char buffer[], int max_len); void Show( Record_type record ); void put_total_rec(int total_rec); int get_total_rec(void); /******************************************************************************* ** ** PURPOSE: To understand the file structure, and practice on implementing ** load data list, find, and add functions. ** ** DESCRIPTION: This is the implementation file of the helper functions ** that are used in implementing a B-Tree. ** *******************************************************************************/ /******************************************************************************* Function: create_tree Task: It creates a B-Tree file and inserts into it the first key *******************************************************************************/ int create_tree(Record_type *rec ) { Item_type item; if((fd_indexfile=_open("bt_index.txt", O_CREAT|O_TRUNC|O_RDWR/*|O_BINARY*/, 0777))<0) Error("\nERROR! can not create b-tree file."); putroot(NIL); PutBtrAvlLst(NIL); PutDtaAvlLst(NIL); //add data availist to btheader get_record(rec); item.key = atoi(rec->RICORDI); item.rec_rrn = 0; return(create_root(item, NIL, NIL)); } /******************************************************************************* Function: getroot Task: It retrieves RRN of the root from the B-Tree header record *******************************************************************************/ int getroot() { BHeader_type btheader; lseek(fd_indexfile, 0L, 0); if(_read(fd_indexfile, &btheader, sizeof(BHeader_type)) < 0) Error("\nERROR! can't get root node.\n"); return(btheader.root); } /******************************************************************************* Function: putroot Task: It writes the RRN of the root into B-Tree header file *******************************************************************************/ void putroot(int root) { BHeader_type btheader; lseek(fd_indexfile, 0L, 0); _read(fd_indexfile, &btheader, sizeof(BHeader_type)); /* Read in B-Tree header */ btheader.root = root; /* Change root in header with given root */ lseek(fd_indexfile, 0L, 0); _write(fd_indexfile, &btheader, sizeof(BHeader_type)); /* Write header back to disk */ } /******************************************************************************* Function: btclose Task: It closes a B-Tree file *******************************************************************************/ void btclose() { close(fd_indexfile); } /******************************************************************************* Function: btopen Task: It opens a B-Tree file. *******************************************************************************/ void btopen() { if((fd_indexfile = _open("bt_index.txt", O_RDWR/*|O_BINARY*/))<0) Error("\nERROR! can not open"); } /******************************************************************************* Function: btread Task: It retrieves a page from the B-Tree file, using the given RRN *******************************************************************************/ int btread(int rrn, page_type *page_ptr) { long addr; addr = (long)rrn * (long)PAGESIZE + (long)sizeof(BHeader_type); lseek(fd_indexfile, addr, 0); return(_read(fd_indexfile, page_ptr, PAGESIZE)); } /******************************************************************************* Function: btwrite Task: It writes a given page to the B-Tree file, using the given RRN *******************************************************************************/ int btwrite(int rrn, page_type *page_ptr) { long addr; addr = (long)rrn * (long)PAGESIZE + (long)sizeof(BHeader_type); lseek(fd_indexfile, addr, 0); return(_write(fd_indexfile, page_ptr, PAGESIZE)); } /******************************************************************************* Function: getpage Task: It returns the RRN of the next available slot in the B-Tree file *******************************************************************************/ int getpage() { int avail_rrn, next_avail_rrn; if( (avail_rrn = GetBtrAvlLst()) == NIL ) /* Checks stack available slot */ avail_rrn = (int)((lseek(fd_indexfile, 0L, 2) - sizeof(BHeader_type)) / PAGESIZE); else { /* If stack's not empty */ GetBtrAvlRec( avail_rrn, &next_avail_rrn ); /* pop stack */ PutBtrAvlLst( next_avail_rrn ); } return(avail_rrn); } /******************************************************************************* Function: GetBtrAvlLst: Task: It returns the top of the avail list stack. *******************************************************************************/ int GetBtrAvlLst(void) { BHeader_type btheader; lseek(fd_indexfile, 0, 0); _read(fd_indexfile, &btheader, sizeof(BHeader_type)); return(btheader.avail_list); } /******************************************************************************* Function: GetBtrAvlRec Task: It retrieves the next available RRN. *******************************************************************************/ void GetBtrAvlRec(int avail_rrn, int *next_avail_rrn) { AvlRec_type avail_rec; long addr; addr = (long)(sizeof(BHeader_type)) + (long)(avail_rrn * PAGESIZE); lseek(fd_indexfile, addr, 0); _read(fd_indexfile, &avail_rec, sizeof(AvlRec_type)); *next_avail_rrn = avail_rec.next; } /******************************************************************************* Function: PutBtrAvlRec Task: It retrieves the next available RRN. *******************************************************************************/ void PutBtrAvlRec(int rrn, int next_avail_rrn) { AvlRec_type avail_rec; long addr; addr = (long)(sizeof(BHeader_type)) + (long)(rrn * PAGESIZE); avail_rec.next = next_avail_rrn; lseek(fd_indexfile, addr, 0); _write(fd_indexfile, &avail_rec, sizeof(AvlRec_type)); } /******************************************************************************* Function: PutBtrAvlLst Task: It places the passed in RRN in the header file ,as the next available page. *******************************************************************************/ void PutBtrAvlLst(int avail_rrn) { BHeader_type btheader; lseek(fd_indexfile, 0, 0); _read(fd_indexfile, &btheader, sizeof(BHeader_type)); btheader.avail_list = avail_rrn; /* Replace the top of the */ /* avail list with a new RRN */ lseek(fd_indexfile, 0, 0); /* Write header back to */ _write(fd_indexfile, &btheader, sizeof(BHeader_type)); /* B-Tree file */ } /*******************************************************************************/ /******************************************************************************* ** ** ** PURPOSE: To understand the file structure, and practice on implementing ** load data list, find, and add functions. ** ** DESCRIPTION: This is the implementation file of the helper functions ** that is used for implementing a B-Tree. ** *******************************************************************************/ /******************************************************************************* Function: inp_open Task: It opens the user given input file that is passed to it, in text mode. *******************************************************************************/ void inp_open(char *filename) { if ((fd_inputfile = _open(filename, O_RDONLY/*|O_TEXT*/)) < 0) Error("\nERROR! can not open input file."); } /******************************************************************************* Function: dta_open Task: It Opens the data file. *******************************************************************************/ void dta_open() { if( (fd_datafile = _open("records.txt", O_CREAT |O_RDWR/*|O_BINARY*/)) < 0) Error("\nError opening data file"); } /******************************************************************************* Function: dta_close Task: It closes the data file. *******************************************************************************/ void dta_close() { close(fd_datafile); } /******************************************************************************* Function: get_field Task: It retrieves field from input file using delimiter character and desired fixed length. *******************************************************************************/ int getfield(char buffer[], int max_len) { int bytes, field_len = 0; char c; while((bytes = (_read(fd_inputfile, &c, 1)) > 0) && ((c == '\t') || (c == '\n'))) /* Do nothing */; if (bytes > 0) buffer[field_len++] = c; while((field_len 0) && (c != '\t') && (c != '\n') ) { if(field_len < max_len - 1) /* Truncate field if more than */ buffer[field_len++] = c; /* fixed-length */ } buffer[field_len] = '\0'; /* Ensure field is NULL terminated */ return(field_len); } /******************************************************************************* Function: get_record Task: It retrieves record from input file field by field. *******************************************************************************/ int get_record( Record_type *record ) { if(!(getfield(record->RYOM, FIELD1_SIZE))) return(0); if(!(getfield(record->FANNA,FIELD2_SIZE))) return(0); if(!(getfield(record->PINCHERLE, FIELD3_SIZE))) return(0); if(!(getfield(record->RICORDI, FIELD4_SIZE))) return(0); if(!(getfield(record->TYPE, FIELD5_SIZE))) return(0); if(!(getfield(record->MUS_KEY, FIELD6_SIZE))) return(0); if(!(getfield(record->OPUS_NUMBER, FIELD7_SIZE))) return(0); return( 1 ); } /******************************************************************************* Function: get_rrn Task: It returns the RRN of the next available record slot in the data file. *******************************************************************************/ int get_rrn( void ) { int avail_rrn; Record_type old_del_rec; avail_rrn = GetDtaAvlLst(); if( avail_rrn == NIL ) /* checks stack for avail rrn */ avail_rrn = get_total_rec(); else{ old_del_rec = RetrievRec(avail_rrn); /*open old rec */ PutDtaAvlLst(atoi(old_del_rec.TYPE));} /* save next del_rrn to availist*/ return( avail_rrn ); /* Return the next avail RRN */ } /******************************************************************************* Function: inp_close Task: It closes the user given input file. *******************************************************************************/ void inp_close() { close(fd_inputfile); } /******************************************************************************* Function: GetDtaAvlLst Task: It returns the top of the avail list stack. *******************************************************************************/ int GetDtaAvlLst(void) { BHeader_type header; lseek(fd_indexfile, 0, 0); /* Get datafile header record*/ _read(fd_indexfile, &header, sizeof(BHeader_type)); /* Return top of avail list */ return(header.data_avail_list); } /******************************************************************************* Function: RetrievRec Task: It reads a record in from the data file using the RRN. *******************************************************************************/ Record_type RetrievRec( int rec_rrn ) { Record_type record; long addr; /* Address of record in file */ int blockNo, rec_num; blockNo = (rec_rrn/4); rec_num = (rec_rrn % 4); addr = (long)((rec_num * RECORDSIZE) + (blockNo * BUFFSIZE)) ; //printf("address : %d\n ", addr); // addr = (long)(rec_rrn * RECORDSIZE); /* Seek directly to record */ lseek(fd_datafile, addr, 0); /* Read in record from data file */ _read(fd_datafile, &record, RECORDSIZE); return(record); } /******************************************************************************* Function: PutDtaAvlLst Task: It places the passed RRN, as the top of the avail list stack. *******************************************************************************/ void PutDtaAvlLst(int avail_rrn) { BHeader_type header; lseek(fd_indexfile, 0, 0); _read(fd_indexfile, &header, sizeof(BHeader_type)); header.data_avail_list = avail_rrn; /* Replace the top of the */ //printf("availist %d",header.data_avail_list); /* avail list with a new RRN */ lseek(fd_indexfile, 0, 0); /* Write header back to */ _write(fd_indexfile, &header, sizeof(BHeader_type)); /* datafile */ } /******************************************************************************* Function: save_record Task: Puts the passed record into the data file at the given RRN. *******************************************************************************/ void save_record(int rec_rrn, Record_type record) { long addr; int blockNo, rec_num; blockNo = (rec_rrn/4); rec_num = (rec_rrn % 4); addr = (long)((rec_num * RECORDSIZE) + (blockNo * BUFFSIZE)); //printf ("rec_rrn %d ",rec_rrn); lseek(fd_datafile, addr, 0); /* Put given record at given */ _write(fd_datafile, &record, RECORDSIZE); /* RRN */ } /*******************************************************************************/ /******************************************************************************* ** ** PURPOSE: To understand the file structure, and practice on implementing ** load data list, find, and add functions. ** ** DESCRIPTION: This is the implementation file of the helper function INSERT ** that is used in inserting nodes to a B-Tree. ** *******************************************************************************/ /******************************************************************************* Function: insert Task: This function is recursively called to insert items into a B-Tree. One Item is inserted at a time. Pre: None Post: If no error occurs (no duplicated record in the tree), then the record is successfully inserted into the B-tree. Otherwise, the function will return an error signal and abort the inserting. *******************************************************************************/ Status_type insert(page_type *parent, int parent_rrn, int parent_pos, Item_type item, int *promo_r_child, Item_type *promo_item) { page_type page, newpage, sibling; Item_type p_b_item; Status_type retval; int found; int pos, p_b_rrn, sibling_rrn, rrn; rrn = parent->child[parent_pos]; if(rrn == NIL) { *promo_item = item; *promo_r_child = NIL; return (FOUND);//(YES); } btread(rrn, &page); found = search_node(item.key, &page, &pos); if(found) return(ERROR); retval = insert(&page, rrn, pos, item, &p_b_rrn, &p_b_item); if((retval == NO_PROMOTION) || (retval == ERROR)) return(retval); if(page.keycount < MAXKEYS) { ins_in_page(p_b_item, p_b_rrn, &page); btwrite(rrn, &page); return(NO_PROMOTION); } else if(Rdstrbt_Ins(p_b_item,p_b_rrn,&page,parent,parent_pos, &sibling,parent_rrn,&sibling_rrn)){ btwrite(parent_rrn, parent); btwrite(rrn, &page); btwrite(sibling_rrn, &sibling); return(NO_PROMOTION); } else { split(p_b_item, p_b_rrn, &page, promo_item, promo_r_child, &newpage); btwrite(rrn, &page); btwrite(*promo_r_child, &newpage); return(PROMOTION); } } /*******************************************************************************/ /******************************************************************************* ** ** PURPOSE: To understand the file structure, and practice on implementing ** the Load, List,Show,Find, Add, Modify and Delete parts function. ** ** DESCRIPTION: This is the implementation file of the helper functions ** that are used in implementing the main functions: Load, List, ** Show, Find, Add, Modify and Delete. ** *******************************************************************************/ #include "btree.h" /******************************************************************************* Function: create_root Task: it gets and initializes root page and inserts one key. *******************************************************************************/ int create_root(Item_type item, int left, int right) { page_type page; int rrn; rrn = getpage(); pageinit(&page); page.item[0] = item; page.child[0] = left; page.child[1] = right; page.keycount = 1; btwrite(rrn, &page); putroot(rrn); return(rrn); } /******************************************************************************* Function: btsearch Task: it searches through B-Tree for the given key. *******************************************************************************/ int btsearch(int rrn, int key, int *found_rrn, int *found_pos) { page_type page; int pos; if( rrn == NIL ) /* base case*/ return(NO); btread(rrn, &page); if(search_node(key, &page, &pos)) { //If key is found in current page, *found_rrn = rrn; //define found_rrn as RRN of page *found_pos = pos; //and found_pos is defined as the return(YES); //position in page, of the key. } else return( btsearch(page.child[pos], key, found_rrn, found_pos) ); } /******************************************************************************* Function: Concatenate Task: it concatenates pages, siblings, and parents if possible, else returns FAILURE. *******************************************************************************/ int Concatenate(page_type *page, page_type *parent, int parent_pos, page_type *sibling, int *sibling_rrn) { if(parent_pos < parent->keycount) { btread(*sibling_rrn = parent->child[parent_pos+1], sibling); if(sibling->keycount == MINKEYS) { Concat_Right(page, parent, sibling, parent_pos); return(1); } } if(parent_pos > 0) { btread(*sibling_rrn = parent->child[parent_pos-1], sibling); if(sibling->keycount == MINKEYS) { Concat_Left(page, parent, sibling, parent_pos-1); return(1); } } return(0); } /******************************************************************************* Function: Concat_Left: Task: it concatenates parent, page and left sibling. *******************************************************************************/ void Concat_Left(page_type *page, page_type *parent, page_type *sibling, int parent_pos) { int i; ins_in_page(parent->item[parent_pos], page->child[0], page); for(i=0;ikeycount;i++) ins_in_page(sibling->item[i], sibling->child[i+1], page); page->child[0] = sibling->child[0]; parent->child[parent_pos] = parent->child[parent_pos+1]; for(i=parent_pos;i<(parent->keycount-1);i++) { parent->item[i] = parent->item[i+1]; parent->child[i+1] = parent->child[i+2]; } (parent->keycount)--; } /******************************************************************************* Function: Concat_Right Task: it concatenates parent, page and right sibling. *******************************************************************************/ void Concat_Right(page_type *page, page_type *parent, page_type *sibling, int parent_pos) { int i; ins_in_page(parent->item[parent_pos], sibling->child[0], page); for(i=0;ikeycount;i++) ins_in_page(sibling->item[i], sibling->child[i+1], page); for(i=parent_pos;i<(parent->keycount-1);i++) { parent->item[i] = parent->item[i+1]; parent->child[i+1] = parent->child[i+2]; } (parent->keycount)--; } /******************************************************************************* Function: Rdstrbt_Del Task: it redistributes, after deletion, between page and it's sibling if possible and returns success else it returns failure. *******************************************************************************/ int Rdstrbt_Del(page_type *page, page_type *parent, int parent_pos, page_type *sibling, int *sibling_rrn) { if(parent_pos < parent->keycount) { btread(*sibling_rrn = parent->child[parent_pos+1], sibling); if(sibling->keycount > MINKEYS) { Rd_Left_Del(sibling, parent, page, parent_pos); return(1); } } if(parent_pos > 0) { btread(*sibling_rrn = parent->child[parent_pos-1], sibling); if(sibling->keycount > MINKEYS) { Rd_Right_Del(sibling, parent, page, parent_pos-1); return(1); } } return(0); } /******************************************************************************* Function: Rdstrbt_Ins: Redistributes during insertion between page and it's sibling if possible and returns success else it returns failure. *******************************************************************************/ int Rdstrbt_Ins(Item_type item, int r_child, page_type *page, page_type *parent, int pos, page_type *sibling, int parent_rrn, int *sibling_rrn) { if(parent_rrn == NIL) return(0); if(pos < parent->keycount) { btread(*sibling_rrn = parent->child[pos+1], sibling); if(sibling->keycount < MAXKEYS) { Rd_Right_Ins(sibling, parent, page, item, r_child, pos); return(1); } } if(pos > 0) { btread(*sibling_rrn = parent->child[pos-1], sibling); if(sibling->keycount < MAXKEYS) { Rd_Left_Ins(sibling, parent, page, item, r_child, pos-1); return(1); } } return(0); } /******************************************************************************* Function: Rd_Left_Del Task: It redistributes between page and it's right sibling. *******************************************************************************/ void Rd_Left_Del(page_type *sibling, page_type *parent, page_type *page, int parent_pos) { int mid, i, j; ins_in_page(parent->item[parent_pos], sibling->child[0], page); mid = (sibling->keycount - page->keycount)/2; for(i=0;iitem[i], sibling->child[i+1], page); parent->item[parent_pos] = sibling->item[mid]; for(i=mid+1,j=0;ikeycount;i++,j++) { sibling->item[j] = sibling->item[i]; sibling->child[j] = sibling->child[i]; } sibling->child[j] = sibling->child[i]; sibling->keycount -= mid + 1; } /******************************************************************************* Function: Rd_Left_Ins Task: It inserts key & r_child then redistributes between page and it's left sibling. *******************************************************************************/ void Rd_Left_Ins(page_type *sibling, page_type *parent, page_type *page, Item_type item, int r_child, int pos) { Item_type workitems[MAXKEYS+1]; int workchild[MAXKEYS+2], mid, i; for(i=0;iitem[i]; workchild[i] = page->child[i]; } workchild[i] = page->child[i]; pageinit(page); for(i=MAXKEYS;item.key0;i--) { workitems[i] = workitems[i-1]; workchild[i+1] = workchild[i]; } workitems[i] = item; workchild[i+1] = r_child; ins_in_page(parent->item[pos], workchild[0], sibling); mid = (MAXKEYS - sibling->keycount)/2; for(i=0;iitem[pos] = workitems[i]; page->child[0] = workchild[i+1]; while(++i < MAXKEYS+1) ins_in_page(workitems[i], workchild[i+1], page); } /******************************************************************************* Function: Rd_Right_Del Task: It redistributes between page and it's left sibling. *******************************************************************************/ void Rd_Right_Del(page_type *sibling, page_type *parent, page_type *page, int parent_pos) { int mid, i; ins_in_page(parent->item[parent_pos], page->child[0], page); mid = (page->keycount + sibling->keycount + 1)/2; for(i=sibling->keycount;i>mid;i--) ins_in_page(sibling->item[i-1], sibling->child[i], page); parent->item[parent_pos] = sibling->item[mid-1]; page->child[0] = sibling->child[mid]; sibling->keycount = mid - 1; } /******************************************************************************* Function: Rd_Right_Ins Task: It inserts key & r_child then redistributes between page and it's right sibling. *******************************************************************************/ void Rd_Right_Ins(page_type *sibling, page_type *parent, page_type *page, Item_type item, int r_child, int pos) { Item_type workitems[MAXKEYS+1]; int workchild[MAXKEYS+2], mid, i; for(i=0;iitem[i]; workchild[i] = page->child[i]; } workchild[i] = page->child[i]; pageinit(page); for(i=MAXKEYS;item.key0;i--) { workitems[i] = workitems[i-1]; workchild[i+1] = workchild[i]; } workitems[i] = item; workchild[i+1] = r_child; ins_in_page(parent->item[pos], sibling->child[0], sibling); mid = (MAXKEYS + sibling->keycount)/2; for(i=MAXKEYS;i>mid;i--) ins_in_page(workitems[i], workchild[i+1], sibling); parent->item[pos] = workitems[i]; sibling->child[0] = workchild[i+1]; while(--i >= 0) ins_in_page(workitems[i], workchild[i+1], page); page->child[0] = workchild[0]; } /******************************************************************************* Function search_node Task: It returns YES if key in page, else NO. In either case, puts key's correct position in pos. *******************************************************************************/ int search_node(int key, page_type *p_page, int *pos) { int i; for(i=0;ikeycount && key>p_page->item[i].key ;i++) ; *pos = i; if(*poskeycount && key == p_page->item[*pos].key) return(YES); else return(NO) ; } /******************************************************************************* Function: split Task: It splits the page by creating new page and moving half of keys to new page. Promote middle key and RRN of new page. *******************************************************************************/ void split(Item_type item, int r_child, page_type *p_oldpage, Item_type *promo_item, int *promo_r_child, page_type *p_newpage) { Item_type workitems[MAXKEYS+1]; int workchild[MAXKEYS+2], i; for(i=0;iitem[i]; workchild[i] = p_oldpage->child[i]; } workchild[i] = p_oldpage->child[i]; for(i=MAXKEYS; item.key 0;i--) { workitems[i] = workitems[i-1]; workchild[i+1] = workchild[i]; } workitems[i] = item; workchild[i+1] = r_child; *promo_r_child = getpage(); pageinit(p_newpage); for(i=0;iitem[i] = workitems[i]; p_oldpage->child[i] = workchild[i]; p_newpage->item[i] = workitems[i+1+MINKEYS]; p_newpage->child[i] = workchild[i+1+MINKEYS]; p_oldpage->item[i+MINKEYS].key = NOKEY; p_oldpage->item[i+MINKEYS].rec_rrn = NIL; p_oldpage->child[i+1+MINKEYS] = NIL; } p_oldpage->child[MINKEYS] = workchild[MINKEYS]; p_newpage->child[MINKEYS] = workchild[i+1+MINKEYS]; p_newpage->keycount = MAXKEYS - MINKEYS; p_oldpage->keycount = MINKEYS; *promo_item = workitems[MINKEYS]; } /******************************************************************************* Function: Swap Task: It swaps the item @ position 'pos' of page with its successor which is in a leaf page. *******************************************************************************/ void Swap(page_type *page, int pos, page_type *leaf, int *leaf_rrn) { Item_type temp; *leaf_rrn = page->child[pos+1]; /* Get right child of page */ btread(*leaf_rrn, leaf); while(leaf->child[0] != NIL) { /* Check to see if a leaf page is */ *leaf_rrn = leaf->child[0]; /* reached, if not continue down */ btread(*leaf_rrn, leaf); /* the B-Tree */ } temp = page->item[pos]; /* When leaf page is reached, swap */ page->item[pos] = leaf->item[0]; /* key with it's successor in the */ leaf->item[0] = temp; /* leaf page */ } /******************************************************************************* Function: Error Task: it prints an error message and terminates program. *******************************************************************************/ void Error( char *s ) { printf( "\n%s\n", s ); exit( 1 ); } /******************************************************************************* Function: FreePage Task: it places empty page into B-Tree avail list. *******************************************************************************/ void FreePage(int rrn) { PutBtrAvlRec(rrn, GetBtrAvlLst()); /* Place top of avail stack @ 'rrn' */ PutBtrAvlLst(rrn); /* Replace top of stack with 'rrn' */ } /******************************************************************************* Function: ins_in_page Task: Inserts key and right child into given page. *******************************************************************************/ void ins_in_page(Item_type item, int r_child, page_type *p_page) { int i; for(i=p_page->keycount; item.key< p_page->item[i-1].key &&i>0;i--) { p_page->item[i] = p_page->item[i-1]; p_page->child[i+1] = p_page->child[i]; } (p_page->keycount)++; p_page->item[i] = item; p_page->child[i+1] = r_child; } /******************************************************************************* Function: pageinit Task: It puts NOKEY in all "key" slots and NIL in "child" slots & sets keycount to zero. *******************************************************************************/ void pageinit(page_type *p_page) { int j; for(j=0; jitem[j].key = NOKEY ; p_page->item[j].rec_rrn = NIL; p_page->child[j] = NIL; } p_page->child[MAXKEYS] = NIL; p_page->keycount = 0; } /*****************************************************************************/ /******************************************************************************* Function search_node1 Task: It returns YES if key in page, else NO. In either case, puts key's correct position in pos. *******************************************************************************/ /******************************************************************************* Function: Show Return type: NONE Task: it displays all the information of a product record that has been passed in. Pre: the product record, record, has been passed in succesfully. Post: the information of that record is output on the screen. *******************************************************************************/ void Show( Record_type record ) { printf("\n\n\n"); printf("Ryom : %s\n",record.RYOM); printf("Fanna: %s\n",record.FANNA); printf("Pincherle: %s\n",record.PINCHERLE); printf("Ricordi: %s\n",record.RICORDI); printf("Type: %s\n",record.TYPE); printf("Key: %s\n",record.MUS_KEY); printf("Opus Number:%s\n",record.OPUS_NUMBER); } /******************************************************************************* Function: Showlist Return type: NONE Task: it displays all the information of a product record that has been passed in. Pre: the product record, record, has been passed in succesfully. Post: the information of that record is output on the screen. *******************************************************************************/ void Showlist( Record_type record ) { printf( "%s %s %s %s %s %s %s\n", record.RICORDI, record.RYOM, record.FANNA, record.PINCHERLE, record.TYPE, record.MUS_KEY, record.OPUS_NUMBER); } /******************************************************************************* Function: put_total_rec Task: It places the passed total record into the bt header. *******************************************************************************/ void put_total_rec(int total_rec) { BHeader_type header; lseek(fd_indexfile, 0, 0); _read(fd_indexfile, &header, sizeof(BHeader_type)); header.total_rec = total_rec; /* insert total record */ /* avail list with a new RRN */ lseek(fd_indexfile, 0, 0); /* Write header back to */ _write(fd_indexfile, &header, sizeof(BHeader_type)); /* datafile */ } /******************************************************************************* Function: get_total_rec Task: It returns the top of the avail list stack. *******************************************************************************/ int get_total_rec(void) { BHeader_type header; lseek(fd_indexfile, 0, 0); /* Get index file header record*/ _read(fd_indexfile, &header, sizeof(BHeader_type)); /* Return top of total_rec */ return(header.total_rec); } #endif