Code:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void insert(char key[9]){
int n,*s,i,*s_temp,s_p,ch,q,tmp,tmp1,test_1,test_2,fl=1,rec_id=33,mem_i[25],mem_i_t[26],j,finished=0,root,b1,b2;
FILE *fp,*f,*ft,*fr;
char *buf,buf1[9],buf2[9],mem[22][9],mem_t[23][9];
//strcpy(key,"NZZZZ!!!");
buf=malloc(sizeof(int));
fp=fopen("index","a+");
//f=fopen("credit3.bin","r");
fr=fopen("root_index","r");
s=malloc(500*sizeof(int));
s_p=-1;
for(i=0;i<=sizeof(int)-1;i++){
ch=fread(&buf[i],1,1,fr);}
memcpy(&root,buf,sizeof(int));
n=root;
fseek(fp,512*(n-1),SEEK_SET);
for(i=0;i<=sizeof(int)-1;i++){
ch=fread(&buf[i],1,1,fp);}
memcpy(&tmp,buf,sizeof(int));
while(tmp!=0){
s_p=s_p+1;
s[s_p]=n;
for(i=0;i<=sizeof(int)-1;i++){
ch=fread(&buf[i],1,1,fp);}
memcpy(&tmp1,buf,sizeof(int));
q=tmp1;
ch=fread(buf1,9,1,fp);
test_1=strncmp(key,buf1,9);
if(test_1<=0){
fseek(fp,162,SEEK_CUR);
for(i=0;i<=(sizeof(int)-1);i++){
ch=fread(&buf[i],1,1,fp);}
memcpy(&tmp1,buf,sizeof(int));
n=tmp1;}
else{
fseek(fp,512*(n-1)+(q-1)*9-1,SEEK_SET); /* Go to K q-1 */
ch=fread(buf1,9,1,fp);
test_1=strncmp(key,buf1,9);
if(test_1>0){
fseek(fp,512*(n-1)+175+q*sizeof(int),SEEK_SET); /* Go to P q */
for(i=0;i<=sizeof(int)-1;i++){
ch=fread(&buf[i],1,1,fp);}
memcpy(&tmp1,buf,sizeof(int));
n=tmp1;}
else{ /* Search i:K i-1 < Key < K i */
i=1;
fseek(fp,512*(n-1)+8,SEEK_SET);
while(i<=q-1 && fl==1){
if(i==1){
ch=fread(buf1,9,1,fp);}
else{
memcpy(buf1,buf2,9);}
ch=fread(buf2,9,1,fp);
test_1=strncmp(key,buf1,9);
test_2=strncmp(key,buf2,9);
if(test_1>0 && test_2<0){
fl=0;
fseek(fp,512*(n-1)+175+(i+1)*sizeof(int),SEEK_SET);
for(j=0;j<=sizeof(int)-1;j++){
ch=fread(&buf[j],1,1,fp);}
memcpy(&tmp1,buf,sizeof(int));
n=tmp1;}
i++;}}}
fseek(fp,512*(n-1),SEEK_SET);
for(i=0;i<=sizeof(int)-1;i++){
ch=fread(&buf[i],1,1,fp);}
memcpy(&tmp,buf,sizeof(int));}
for(i=0;i<=sizeof(int)-1;i++){ /* Search leaf node ( Key == K i ) */
ch=fread(&buf[i],1,1,fp);}
memcpy(&tmp,buf,sizeof(int));
q=tmp;
fl=1;
i=1;
while(i<=q && fl==1){
ch=fread(buf1,9,1,fp);
test_1=strncmp(key,buf1,9);
if(test_1==0){
fl=0;
printf("Key already exists\n");}
i++;}
if(fl==1){ /* If key does not exist , we add it in the tree */
if(q<22){ /* If leaf node is not full we place the new record */
ft=fopen("temp","a+");
fseek(fp,0,SEEK_SET);
while(ftell(fp)<512*(n-1)){
putc(getc(fp),ft);}
for(i=0;i<=sizeof(int)-1;i++){
ch=fread(&buf[i],1,1,fp);}
memcpy(&mem_i[0],buf,sizeof(int));
mem_i[1]=q+1;
fseek(fp,202,SEEK_CUR);
for(j=0;j<=22;j++){
for(i=0;i<=sizeof(int)-1;i++){
ch=fread(&buf[i],1,1,fp);}
memcpy(&mem_i[j+2],buf,sizeof(int));}
fseek(fp,512*(n-1)+8,SEEK_SET);
for(j=0;j<=21;j++){
ch=fread(mem[j],9,1,fp);}
fl=1;
i=0;
tmp=0;
while(fl==1 && i<(q-1)){
test_1=strncmp(key,mem[i],9);
if(test_1>0){
test_2=strncmp(key,mem[i+1],9);
if(test_2<0){
fl=0;}}
else{
tmp=1;
fl=0;}
i++;}
if(fl==1){
mem_i[q+2]=rec_id;
strcpy(mem[q],key);}
if(fl==0){
for(j=(q-1);j>=i-1*tmp;j--){
mem_i[j+3]=mem_i[j+2];
strcpy(mem[j+1],mem[j]);}
mem_i[j+3]=rec_id;
strcpy(mem[j+1],key);}
fwrite(&mem_i[0],sizeof(int),1,ft);
fwrite(&mem_i[1],sizeof(int),1,ft);
for(i=0;i<=21;i++){
fwrite(mem[i],1,9,ft);}
for(i=2;i<=24;i++){
fwrite(&mem_i[i],sizeof(int),1,ft);}
for(i=1;i<=214;i++){
putc(0,ft);}
fseek(fp,512*n,SEEK_SET);
fseek(ft,512*n,SEEK_SET);
while(feof(fp)==0){
tmp=getc(fp);
if(tmp!=-1){
putc(tmp,ft);}}
fclose(ft);
fclose(fp);
remove("index");
rename("temp","index");
fp=fopen("index","a+");}
else{ /* Else we split the leaf node */
ft=fopen("temp","a+");
fseek(fp,0,SEEK_SET);
while(ftell(fp)<512*(n-1)){
putc(getc(fp),ft);}
for(i=0;i<=sizeof(int)-1;i++){
ch=fread(&buf[i],1,1,fp);}
memcpy(&mem_i_t[0],buf,sizeof(int));
mem_i[1]=q+1;
fseek(fp,202,SEEK_CUR);
for(j=0;j<=22;j++){
for(i=0;i<=sizeof(int)-1;i++){
ch=fread(&buf[i],1,1,fp);}
memcpy(&mem_i_t[j+2],buf,sizeof(int));}
fseek(fp,512*(n-1)+8,SEEK_SET);
for(j=0;j<=21;j++){
ch=fread(mem_t[j],9,1,fp);}
fl=1;
i=0;
tmp=0;
while(fl==1 && i<q){
test_1=strncmp(key,mem_t[i],9);
if(test_1>0){
test_2=strncmp(key,mem_t[i+1],9);
if(test_2<0){
fl=0;}}
else{
tmp=1;
fl=0;}
i++;}
b1=n;
tmp1=ftell(fp);
fseek(fp,0,SEEK_END);
b2=ftell(fp)/512+1;
fseek(fp,tmp1,SEEK_SET);
if(fl==1){
mem_i_t[q+3]=rec_id;
strcpy(mem_t[q+1],key);}
if(fl==0){
for(j=q-1;j>=i-tmp;j--){
mem_i_t[j+4]=mem_i_t[j+3];
strcpy(mem_t[j+1],mem_t[j]);}
mem_i_t[j+3]=rec_id;
strcpy(mem_t[j+1],key);}
fseek(fp,306,SEEK_CUR);
tmp=0;
fwrite(&tmp,sizeof(int),1,ft);
tmp=12;
fwrite(&tmp,sizeof(int),1,ft);
for(i=0;i<=11;i++){
fwrite(mem_t[i],1,9,ft);}
for(i=1;i<=90;i++){
putc(0,ft);}
for(i=2;i<=13;i++){
fwrite(&mem_i_t[i],sizeof(int),1,ft);}
for(i=1;i<=40;i++){
putc(0,ft);}
tmp=ftell(fp)/512+1;
fwrite(&tmp,sizeof(int),1,ft);
for(i=1;i<=214;i++){
putc(0,ft);}
while(feof(fp)==0){
tmp=getc(fp);
if(tmp!=-1){
putc(tmp,ft);}}
tmp=0;
fwrite(&tmp,sizeof(int),1,ft);
tmp=11;
fwrite(&tmp,sizeof(int),1,ft);
for(i=0;i<=10;i++){
fwrite(mem_t[i+12],1,9,ft);}
for(i=1;i<=99;i++){
putc(0,ft);}
for(i=14;i<=24;i++){
fwrite(&mem_i_t[i],sizeof(int),1,ft);}
for(i=1;i<=44;i++){
putc(0,ft);}
fwrite(&mem_i_t[25],sizeof(int),1,ft);
for(i=1;i<=214;i++){
putc(0,ft);}
strcpy(key,mem_t[11]);
do{ /* Insert key in the parent node */
if(s_p==-1){
tmp=1;
fwrite(&tmp,sizeof(int),1,ft);
tmp=2;
fwrite(&tmp,sizeof(int),1,ft);
fwrite(key,1,9,ft);
for(i=1;i<=162;i++){
putc(0,ft);}
fwrite(&n,sizeof(int),1,ft);
tmp1=ftell(fp);
fseek(fp,0,SEEK_END);
tmp=ftell(fp)/512+1;
fseek(fp,tmp1,SEEK_SET);
fwrite(&tmp,sizeof(int),1,ft);
for(i=1;i<=325;i++){
putc(0,ft);}
root=tmp+1;
finished=1;}
else{ /* If parent node is not full , we place the new record */
n=s[s_p];
s_p--;
fseek(fp,512*(n-1)+4,SEEK_SET);
for(i=0;i<=sizeof(int)-1;i++){
ch=fread(&buf[i],1,1,fp);}
memcpy(&tmp,buf,sizeof(int));
q=tmp;
if(q<20){
fclose(fp);
fclose(ft);
remove("index");
rename("temp","index");
fp=fopen("index","a+");
ft=fopen("temp","a+");
while(ftell(fp)<512*(n-1)){
putc(getc(fp),ft);}
for(i=0;i<=sizeof(int)-1;i++){
ch=fread(&buf[i],1,1,fp);}
memcpy(&mem_i[0],buf,sizeof(int));
mem_i[1]=q+1;
fseek(fp,175,SEEK_CUR);
for(j=0;j<=19;j++){
for(i=0;i<=sizeof(int)-1;i++){
ch=fread(&buf[i],1,1,fp);}
memcpy(&mem_i[j+2],buf,sizeof(int));}
fseek(fp,512*(n-1)+8,SEEK_SET);
for(j=0;j<=21;j++){
ch=fread(mem[j],9,1,fp);}
fl=1;
i=0;
tmp=0;
while(fl==1 && i<(q-1)){
test_1=strncmp(key,mem[i],9);
if(test_1>0){
test_2=strncmp(key,mem[i+1],9);
if(test_2<0){
fl=0;}}
else{
tmp=1;
fl=0;}
i++;}
if(fl==1){
mem_i[q+2]=b2;
strcpy(mem[q],key);}
if(fl==0){
for(j=(q-1);j>=i-1*tmp;j--){
mem_i[j+4]=mem_i[j+3];
strcpy(mem[j+1],mem[j]);}
mem_i[j+4]=b2;
mem_i[j+3]=b1;
strcpy(mem[j+1],key);}
fwrite(&mem_i[0],sizeof(int),1,ft);
fwrite(&mem_i[1],sizeof(int),1,ft);
for(i=0;i<=18;i++){
fwrite(mem[i],1,9,ft);}
for(i=2;i<=22;i++){
fwrite(&mem_i[i],sizeof(int),1,ft);}
for(i=1;i<=249;i++){
putc(0,ft);}
fseek(fp,512*n,SEEK_SET);
fseek(ft,512*n,SEEK_SET);
while(feof(fp)==0){
tmp=getc(fp);
if(tmp!=-1){
putc(tmp,ft);}}
finished=1;}
else{ /* If parent is full , we split again */
fclose(fp);
fclose(ft);
remove("index");
rename("temp","index");
fp=fopen("index","a+");
ft=fopen("temp","a+");
while(ftell(fp)<512*(n-1)){
putc(getc(fp),ft);}
for(i=0;i<=sizeof(int)-1;i++){
ch=fread(&buf[i],1,1,fp);}
memcpy(&mem_i_t[0],buf,sizeof(int));
mem_i[1]=q+1;
fseek(fp,175,SEEK_CUR);
for(j=0;j<=19;j++){
for(i=0;i<=sizeof(int)-1;i++){
ch=fread(&buf[i],1,1,fp);}
memcpy(&mem_i_t[j+2],buf,sizeof(int));}
fseek(fp,512*(n-1)+8,SEEK_SET);
for(j=0;j<=19;j++){
ch=fread(mem_t[j],9,1,fp);}
fl=1;
i=0;
tmp=0;
while(fl==1 && i<q){
test_1=strncmp(key,mem_t[i],9);
if(test_1>0){
test_2=strncmp(key,mem_t[i+1],9);
if(test_2<0){
fl=0;}}
else{
tmp=1;
fl=0;}
i++;}
tmp1=ftell(fp);
fseek(fp,0,SEEK_END);
b2=ftell(fp)/512;
fseek(fp,tmp1,SEEK_SET);
if(fl==1){
mem_i_t[q+3]=b2;
strcpy(mem_t[q+1],key);}
if(fl==0){
for(j=q-1;j>=i-tmp;j--){
mem_i_t[j+4]=mem_i_t[j+3];
strcpy(mem_t[j+1],mem_t[j]);}
//mem_i_t[j+3]=b1;
mem_i_t[j+4]=b2;
strcpy(mem_t[j+1],key);}
tmp=1;
fwrite(&tmp,sizeof(int),1,ft);
tmp=10;
fwrite(&tmp,sizeof(int),1,ft);
for(i=0;i<=8;i++){
fwrite(mem_t[i],1,9,ft);}
for(i=1;i<=90;i++){
putc(0,ft);}
for(i=2;i<=11;i++){
fwrite(&mem_i_t[i],sizeof(int),1,ft);}
for(i=1;i<=40;i++){
putc(0,ft);}
for(i=1;i<=249;i++){
putc(0,ft);}
fseek(fp,324,SEEK_CUR);
while(feof(fp)==0){
tmp=getc(fp);
if(tmp!=-1){
putc(tmp,ft);}}
tmp=1;
fwrite(&tmp,sizeof(int),1,ft);
tmp=11;
fwrite(&tmp,sizeof(int),1,ft);
for(i=0;i<=9;i++){
fwrite(mem_t[i+10],1,9,ft);}
for(i=1;i<=81;i++){
putc(0,ft);}
for(i=12;i<=22;i++){
fwrite(&mem_i_t[i],sizeof(int),1,ft);}
for(i=1;i<=79;i++){
putc(0,ft);}
for(i=1;i<=214;i++){
putc(0,ft);}
b1=n;
strcpy(key,mem_t[8]);}}
}while(finished==0);
fclose(fp);
fclose(ft);
remove("index");
rename("temp","index");
fp=fopen("index","a+");}}
fclose(fr);
fr=fopen("root_index","w+");
fwrite(&root,sizeof(int),1,fr);
free(buf);
free(s);
fclose(fr);
fclose(fp);
//fclose(f);
}
main(){
FILE *f,*fp,*fr;
int i=1,ch,a[1],b[1],j;
char mem[9];
f=fopen("credit3.bin","rb");
fp=fopen("index","w+");
fr=fopen("root_index","w+");
ch=fread(mem,9,1,f);
a[0]=0;
b[0]=1;
fwrite(a,sizeof(int),1,fp);
fwrite(b,sizeof(int),1,fp);
fwrite(mem,1,9,fp);
for(j=1;j<=189;j++){
putc(0,fp);}
a[0]=1;
fwrite(a,sizeof(int),1,fp);
for(j=1;j<=302;j++){
putc(0,fp);}
a[0]=1;
fwrite(&a,sizeof(int),1,fr);
fclose(fp);
fclose(fr);
while(feof(f)==0){
fseek(f,51*i,SEEK_SET);
i++;
ch=fread(mem,9,1,f);
insert(mem);}
fclose(f);
}