b+tree_unix.zip_B_tree_The Program_b+tree

#include <stdio.h> #include <curses.h> #include <string.h> #include <sys/types.h> #include <malloc.h> #include <unistd.h> #define printr(x) { printw(x); refresh(); getch(); return; } #define MAX_REC_PER_IDX 6 #define LOW_HALF (MAX_REC_PER_IDX - (int)((MAX_REC_PER_IDX + 1)/2) - 1) #define HIGH_HALF (MAX_REC_PER_IDX - LOW_HALF) #define NULL_ADDRESS -1 /* A pointer to a node in this scheme is the position of that node in the file. Since position can be 0, NULL pointers are indicated by negative values. */ typedef struct { long key_val; /* key feild: corresponds to i.d. number of a student. */ int address; /* For a leaf node: address of the corresponding record in the data file. For a non-leaf node: address of the "son" node in the index file. */ } Idx_Rec; typedef struct { int height; /* current level of node equals 1 if the node is a leaf */ int counter; Idx_Rec key_rec[MAX_REC_PER_IDX]; int next; /* pointer to next leaf node */ int parent; /* pointer to the parent in the tree */ } Idx_Node; typedef struct { long stud_id; char last_name[10]; char first_name[10]; char street[10]; int house_number; char town[10]; } SPD; /* Student Personal Details */ #define false 0 #define true 1 typedef unsigned char boolean; FILE *std, *ind; int ins_flag = 0; long idx_size = sizeof(Idx_Node), spd_size = sizeof(SPD); main(argc, argv) int argc; char **argv; { char c; if ((std = fopen(argv[1], "w+b")) == NULL) { printf("Can't open master file %s\n", argv[1]); return; } if ((ind = fopen(argv[2], "w+b")) == NULL) { printf("Can't open index file %s\n", argv[2]); return; } initscr(); /* initalize the text graphics package */ cbreak(); /* set mode for immediate passing symbols to the program */ while (1) { erase(); /* clear the virtual screen */ /* output the menu window on the virtual screen */ mvaddstr(1, 20, "WELCOME TO THE STUDENTS DETAILS PROCESSING SYSTEM\n"); mvaddstr(3, 24, "+---------- MAIN MENU ----------+"); mvaddstr(4, 24, "| 1. Search a record |"); mvaddstr(5, 24, "| 2. Add a record |"); mvaddstr(6, 24, "| 3. Delete a record |"); mvaddstr(7, 24, "| 4. Sequential output |"); mvaddstr(8, 24, "| 5. Tree representation |"); mvaddstr(9, 24, "| 6. Exit from the program |"); mvaddstr(10, 24, "+-------------------------------+"); mvaddstr(12, 30, "Choose your option > "); refresh(); /* dump the virtual screen on the physical screen */ c = getch(); /* get a key */ if (c == '6') /* if '5' then exit */ { endwin(); /* close the package */ return; /* terminate the program */ } if (c > '5' || c < '1') /* if not the right symbol - get another */ continue; /* choose the appropriate function */ switch (c) { /* case '1' : Search_A_Record(); break; */ case '2' : Add_A_Record(); break; case '3' : Delete_A_Record(); break; case '4' : Sequential_Output(); break; /* case '5' : Tree_Representation(); break; */ } } } Delete_A_Record() { /* print the message and exit */ printr("\nThis task is temporarily not avaliable\nPress any key..."); } Sequential_Output() { Idx_Node header, node; int pointer, i; SPD record; if (!fread(&header, idx_size, 1, ind)) { printf("Index file %s is empty\n", index); return; } pointer = header.next; fseek(ind, header.next, SEEK_SET); fread(&node, idx_size, 1, ind); while (node.height != 1) { pointer = (node.key_rec[0]).address; fseek(ind, pointer, SEEK_SET); fread(&node, idx_size, 1, ind); } do { for(i=0; i<node.counter; i++) { fseek(ind, pointer, SEEK_SET); fread(&node, idx_size, 1, ind); fseek(std, (node.key_rec[i]).address, SEEK_SET); fread(&record, spd_size, 1, std); printf("%d %10s %10s %d", record.stud_id, record.last_name, record.first_name, (node.key_rec[i]).address); } pointer = node.next; } while (pointer != NULL_ADDRESS); } Add_A_Record() { Idx_Node header, node; Idx_Node *pointer, *blck, *new_root; Idx_Rec maximal; SPD record; int i, j, rec_adr, fadr; i = fseek(std, 0, SEEK_END); j = fseek(ind, 0, SEEK_END); if ((i == 0 && j != 0) || (i != 0) && (j == 0)) { printf("The master and the index files are not appropriate\n"); exit(-1); } fseek(std, 0, SEEK_SET); fseek(ind, 0, SEEK_SET); if (i == 0 && j == 0) { header.next = NULL_ADDRESS; fwrite(&header, idx_size, 1, ind); } else fread(&header, idx_size, 1, ind); printf("Enter ID number to add > "); scanf("%d", &record.stud_id); /* if (!Search_A_Record(record.stud_id)) { printf("The record already exists.\n"); return(1); } else */ { printf("Enter the student's last name > "); scanf("%10s", record.last_name); printf("Enter the student's first name > "); scanf("%10s", record.first_name); printf("Enter the street name > "); scanf("%10s", record.street); printf("Enter the house number > "); scanf("%d", record.house_number); printf("Enter the town name > "); scanf("%10s", record.town); } fseek(std, 0, SEEK_END); rec_adr = ftell(std); fwrite(&record, spd_size, 1, std); if (header.next == NULL_ADDRESS) { node.height = 1; node.counter = 1; node.next = NULL_ADDRESS; node.parent = NULL_ADDRESS; for (i=1; i<MAX_REC_PER_IDX; i++) (node.key_rec[i]).address = NULL_ADDRESS; header.next = ftell(ind); fseek(ind, 0, SEEK_SET); fwrite(&header, idx_size, 1, ind); (node.key_rec[0]).key_val = record.stud_id; (node.key_rec[0]).address = rec_adr; fwrite(&node, idx_size, 1, ind); } else { fread(&node, idx_size, 1, ind); if (node.height == 1) { if (node.counter < MAX_REC_PER_IDX) { i = 0; while (1) { if (record.stud_id < (node.key_rec[i]).key_val) { for(j=node.counter; j>i; j--) { (node.key_rec[j]).key_val = (node.key_rec[j-1]).key_val; (node.key_rec[j]).address = (node.key_rec[j-1]).address; } (node.key_rec[i]).key_val = record.stud_id; (node.key_rec[i]).address = rec_adr; (node.counter)++; break; } if (++i == node.counter) { i--; break; } } fseek(ind, idx_size, SEEK_SET); fwrite(&node, idx_size, 1, ind); } else { maximal = node.key_rec[node.counter-1]; new_root = (Idx_Node *) malloc(idx_size); blck = (Idx_Node *) malloc(idx_size); for(i=HIGH_HALF; i<MAX_REC_PER_IDX; i++) { (blck->key_rec[i-HIGH_HALF]).key_val = (node.key_rec[i]).key_val; (blck->key_rec[i-HIGH_HALF]).address = (node.key_rec[i]).address; } node.counter = HIGH_HALF; blck->counter = LOW_HALF; blck->height = node.height; /* leaf node */ blck->next = NULL_ADDRESS; fseek(ind, 0, SEEK_END); node.next = ftell(ind); fseek(ind, idx_size, SEEK_SET); node.parent = ftell(ind);