// Example b-tree
// using ftello(), fseeko(), fread(), fwrite().
// Copyright (c)  2007, 2008 Kevin C. O'Kane
/*
    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/


#define _FILE_OFFSET_BITS 64
#define _LARGE_FILE_SUPPORT

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <time.h>

// -------------- BTREE PARAMETERS ---------------------

// NBR_ITEMS must be even 
#define NBR_ITEMS 10
#define KEY_SIZE 32
#define FNAME 128
#define BUF_SIZE 128
#define TREE_NAME "btree.dat"
// #define PRINT

#define STORE 0
#define RETRIEVE 1
#define DELETE 2
#define CLOSE 3
#define TREEPRINT 4

struct entry {
        char key[KEY_SIZE];
        off_t data;
        };

struct block {
        struct entry item[NBR_ITEMS+1];
        off_t pointer[NBR_ITEMS+2];
        };

static struct block tmp2;
static struct entry up;
static off_t loc1;

int add_rec(FILE *, off_t , char *, off_t );
struct entry * search(FILE *,char *, off_t);
void dump(char *, FILE *f,off_t root);
void dump1(off_t, struct block);
struct entry * Btree(int, char *, off_t);
void printTree(FILE *bt, off_t root);

// -------------- BTREE PARAMETERS ---------------------

int MAX,MAX1;

int main() {

        FILE *input;
        char buf[BUF_SIZE];
        char key[KEY_SIZE];
        off_t data;
        char * p1;
        time_t t1,t2;
int i=0;

        t1=time(NULL);
        input=fopen("btreedata","r");

        while (fgets(buf,BUF_SIZE,input)!=NULL) { // read input file
i++;

                buf[strlen(buf)-1] = '\0'; // chop new line
#ifdef PRINT
                printf("add ------------------------> ");
                puts(buf);
#endif

                p1=strtok(buf,","); // tokens will be delimited by commas
                if (p1==NULL || strlen(p1)>KEY_SIZE-1) { 
                        printf("Error on input\n");
                        return EXIT_FAILURE;
                        }

                strcpy(key,p1);

                p1=strtok(NULL,",");
                if (p1==NULL || strlen(p1)>KEY_SIZE-1) {
                        printf("Error on input\n");
                        return EXIT_FAILURE;
                        }

                sscanf(p1,"%lld",&data);

            if (Btree(STORE,key,data) == NULL) return EXIT_FAILURE;

            }

        printf("BEGIN RETRIEVE PHASE\n");

        rewind(input);  // go back to start of input file

        MAX=MAX1=0;

        while (fgets(buf,BUF_SIZE,input)!=NULL) { // read input file

                struct entry *t1;
                MAX=0;

                buf[strlen(buf)-1] = '\0'; // chop new line
                p1=strtok(buf,","); // tokens will be delimited by commas
                if ( (t1=Btree(RETRIEVE,p1,0)) ==NULL) {
                        printf("not found %s\n",p1);
                        return EXIT_FAILURE;
                        }
#ifdef PRINT
                else printf("%s %lld\n",t1->key,t1->data);
#endif
                if (MAX>MAX1) MAX1=MAX;
                }

      Btree(TREEPRINT,NULL,0);

      printf("Maximum tree depth = %d\n",MAX1);
      Btree(CLOSE,p1,0);
      printf("Total time=%d\n",time(NULL)-t1);
      return EXIT_SUCCESS;
      }

//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

struct entry * Btree(int action, char *key, off_t data) {

      static FILE * btree = NULL;
      off_t root;

      if (action == CLOSE) {
            if ( btree != NULL ) fclose (btree);
            btree = NULL;
            return NULL;
            }

      if (action == RETRIEVE) {
            if ( btree == NULL ) return NULL;
            return search(btree,key,0);
            }

      if (btree == NULL ) {                            // file not open 

            if ( access(TREE_NAME,F_OK) ) {            // true if file not found

                  btree=fopen(TREE_NAME,"w+");         // open for create read/write
                  if (btree==NULL) {
                        printf("Error on btree file\n");
                        return NULL;
                        }
                  root = -1;                           // has no root block yet

                  /* first 8 bytes of file hold the disk pointer to the root block. */

                  fwrite(&root,sizeof(off_t),1,btree); // create root record
                  }

            /* file exists - do not re-create */

            else {
                  btree=fopen(TREE_NAME,"r+");
                  if (btree==NULL) {
                        printf("Error on btree file\n");
                        return NULL;
                        }
                  }
            }

            if (action == TREEPRINT) {

                  fseeko(btree,0,SEEK_SET);           // root
                  fread(&root,sizeof(off_t),1,btree); 

                  printTree(btree,root);
                  return NULL;
                  }

            if (action != STORE) return NULL;

            if (add_rec(btree,0,key,data)) { // 0 means use root

                  /* special case - if add_rec() returns non-zero it means
                     a root split is needed 
                  */

                  off_t root;
                  int j;

                  fseeko(btree,0,SEEK_SET);  // old root
                  fread(&root,sizeof(off_t),1,btree); // advances fp

                  for (j=1; j<NBR_ITEMS+1; j++) { // zap it
                        tmp2.pointer[j]=-1;
                        tmp2.item[j].key[0]='\0';
                        tmp2.item[j].data=-1;
                        }
                  strcpy(tmp2.item[0].key,up.key);  // key sent up from below
                  tmp2.item[0].data=up.data;        // data sent up from below
                  tmp2.pointer[0]=loc1;             // less than child
                  tmp2.pointer[1]=root;             // old root block

                  fseeko(btree,0,SEEK_END);         // find eof
                  root=ftello(btree);
                  fwrite(&tmp2,sizeof(struct block),1,btree); // write new root

                  fseek(btree,0,SEEK_SET);
                  fwrite(&root,sizeof(off_t),1,btree); // new root 
                }

      strcpy(up.key,key);
      up.data=data;
      return &up;
      }

int add_rec(FILE *f, off_t start, char *key, off_t data) {

      off_t root,off1,off2,off3;
      int i,j,k;
      struct block tmp1;
      int flg1;

      loc1=-1;

      /* if start is zero, we load the address of the root block
         into root 
      */

      if (start==0) { 
            fseeko(f,0,SEEK_SET);           // move to beginning of file
            fread(&root,sizeof(off_t),1,f); // reading advances the fp
            }
      else root=start;  // begin with a block other than root

      /* if root is -1, special case - no tree exists yet - make
         the first (root) block.
      */

      if (root == -1 ) {

                /* build a block in tmp1
                   copy key into first slot
                   copy data into first slot
                   make child ptr -1 (points to nothing)
                */

                strcpy(tmp1.item[0].key,key);  // key
                tmp1.item[0].data=data;        // data pointer
                tmp1.pointer[0]=-1;            // child

                /* zero-out the remainder of the block */

                for (i=1; i<NBR_ITEMS+1; i++) {  // zero the rest
                        tmp1.item[i].key[0]='\0';
                        tmp1.item[i].data=-1;
                        tmp1.pointer[i]=-1;
                        }
                tmp1.pointer[NBR_ITEMS+1]=-1;    // top end down pointer

                /* write this record out and put its address in the root
                   address ares (first 8 bytes).
                */

                root=ftello(f);                          // where are we?
                fwrite(&tmp1,sizeof(struct block),1,f);  // write first block

                fseek(f,0,SEEK_SET);                     // move to beginning
                fwrite(&root,sizeof(off_t),1,f);         // new root
                return 0;                                // done
                }

        /* a tree exists */

        fseeko(f,root,SEEK_SET);                        // move to root address
        fread(&tmp1,sizeof(struct block),1,f);          // read block
        flg1=0;

        /* start searching this block */

        for (i=0; i<NBR_ITEMS; i++) {

                if ( strlen(tmp1.item[i].key)==0) {
                        flg1=1; // empty key found - end of keys
                        break;
                        }

                if ( (j=strcmp(key,tmp1.item[i].key)) == 0 ) { // compare keys
                        tmp1.item[i].data=data; // found - just update data pointer
                        fseeko(f,root,SEEK_SET);
                        fwrite(&tmp1,sizeof(struct block),1,f);
                        return 0; // done
                        }

                if (j>0) continue; // search key greater than recorded key
                break; // search key less than recorded key
                       // not in this block
                }

            if (tmp1.pointer[i]>=0) { // lower block exists - descend
                  if ( add_rec(f,tmp1.pointer[i],key,data)==0 ) // if not 0, a key was sent up
                        return 0; // finished - no key sent up.
                  strcpy(key,up.key); // a split occurred below and this key was sent up
                  data=up.data;       // data pointer sent up
                  }

      // insert into long block - block has one extra slot

      for (j=NBR_ITEMS; j>=i; j--) { // shift to create opening
            tmp1.pointer[j]=tmp1.pointer[j-1];
            tmp1.item[j]=tmp1.item[j-1];
            }

      tmp1.pointer[i]=loc1;          // child ptr - zero or sent from below
      strcpy(tmp1.item[i].key,key);  // key being added
      tmp1.item[i].data=data;        // data being added

      for (k=0; k<NBR_ITEMS+1; k++) 
            if (strlen(tmp1.item[k].key)==0) break; // find end of block (k)

      if (k<NBR_ITEMS) {  // easy insert - block had space
            fseeko(f,root,SEEK_SET);
            fwrite(&tmp1,sizeof(struct block),1,f);
            return 0; // block ok
            }

      // split block - block full


      strcpy(up.key,tmp1.item[NBR_ITEMS/2].key);  // key to be sent up
      up.data=tmp1.item[NBR_ITEMS/2].data;        // data to be sent up

      // tmp2 will be the low order block resulting from the split

      for (j=0; j <= NBR_ITEMS/2; j++) {  // copy low order data from tmp1

            tmp2.pointer[j]=tmp1.pointer[j];
            tmp2.item[j]=tmp1.item[j];  // structure copy
            }

      for (j = NBR_ITEMS/2+1; j < NBR_ITEMS+1; j++) { // zap the remainder
            tmp2.pointer[j]=-1;
            tmp2.item[j].key[0]='\0';
            tmp2.item[j].data=-1;
            }

      tmp2.item[NBR_ITEMS/2].key[0]=0;
      tmp2.item[NBR_ITEMS/2].data=-1;

      fseeko(f,0,SEEK_END); // advance to endfile and record location
      loc1=ftello(f);

      fwrite(&tmp2,sizeof(struct block),1,f); // write low block out

      // tmp1 is the high order block resulting from the split

      for (j=0; j<NBR_ITEMS/2; j++) {  // shift its contents down to beginning
            tmp1.pointer[j]=tmp1.pointer[NBR_ITEMS/2+j+1];
            tmp1.item[j]=tmp1.item[NBR_ITEMS/2+j+1];
            }

      for (j=NBR_ITEMS/2; j<NBR_ITEMS+1; j++) { // zap its high items
            tmp1.pointer[j]=-1;
            tmp1.item[j].key[0]='\0';
            tmp1.item[j].data=-1;
            }

      tmp1.pointer[NBR_ITEMS/2+1]=tmp1.pointer[NBR_ITEMS+1]; // move its high end child ptr
      tmp1.pointer[NBR_ITEMS+1]=-1; // zap it
      tmp1.item[NBR_ITEMS+1],key[0]=0; // zap it
      fseeko(f,root,SEEK_SET);
      fwrite(&tmp1,sizeof(struct block),1,f); // write high half
      return 1;  // key/data/child ptr being sent up
      }

struct entry * search(FILE * f, char *key, off_t root) {

      off_t off1,off2,off3;
      int i,j;
      static struct block tmp1;
      int flg1;

      MAX++;

      if (root==0) {
            fseeko(f,0,SEEK_SET);
            fread(&root,sizeof(off_t),1,f); // advances fp
            }

            fseeko(f,root,SEEK_SET);
            fread(&tmp1,sizeof(struct block),1,f);
            flg1=0;
            for (i=0; i<NBR_ITEMS; i++) {

                  if ( strlen(tmp1.item[i].key)==0) { flg1=1; break; } // empty key

                  if ( (j=strcmp(key,tmp1.item[i].key)) == 0 ) {
                        return &tmp1.item[i];
                        }
                  if (j>0) continue;
                  break;
                  }

            if (tmp1.pointer[i]>=0) { // descend - may be high key
                  root=tmp1.pointer[i];
                  return search(f,key,root);
                  }
            return NULL;
       }

void dump(char * cap, FILE *f,off_t root) {
      struct block tmp;
      int i;
      fseeko(f,root,SEEK_SET);
      fread(&tmp,sizeof(struct block),1,f);
      printf("***dump=%s from block nbr %lld\n",cap,root);
      for (i=0; i<NBR_ITEMS+1; i++) {
            printf("%d key=%s %lld %lld\n",i,tmp.item[i].key,tmp.item[i].data,tmp.pointer[i]);
            }
      return;
      }

void dump1(off_t r, struct block tmp) {
      int i;
      printf("\n***dump from block %lld***\n",r);
      for (i=0; i<NBR_ITEMS+1; i++) {
            printf("%d key=%s %lld %lld\n",i,tmp.item[i].key,tmp.item[i].data,tmp.pointer[i]);
            }
      return;
      }

void printTree(FILE *bt, off_t root) {

      int i;
      struct block tmp1;

            fseeko(bt,root,SEEK_SET);
            fread(&tmp1,sizeof(struct block),1,bt);

            for (i=0; i<NBR_ITEMS; i++) {

                  if ( strlen(tmp1.item[i].key)==0) { // empty key
                        if (tmp1.pointer[i] > 0 ) printTree(bt, tmp1.pointer[i]);
                        return;
                        }

                  if (tmp1.pointer[i] > 0 ) printTree(bt, tmp1.pointer[i]);

                  printf("%s,%lld\n", tmp1.item[i].key, tmp1.item[i].data);

                  }

            return;

      }