#include <stdio.h>  /* Include the stdio library */
#include <stdlib.h> /* Include the stdlib library */
#include "../include/pvm3.h" /* Include the pvm3 library */

#define SLAVE "cryptoslave" /* The program which the slave processes
                               run */
#define PROC 10  /* The number of slave processes */

/* Each node holds 4 variables: data[] holds a data string which has to
   be searched, next holds the next node in the queue, and last holds the
   preceeding node in the queue */

typedef struct node {
    char data[1000];
    struct node *next;
    struct node *last;
} Node;

/* Queue functions. putqueue() puts an item at the front of the queue,
   getqueue() takes an item off the end of the queue, and isempty()
   returns 1 if the queue is empty */

void putqueue(Node **Head, char newdata[1000]);
int isempty(Node *Head, Node *Tail);
void getqueue(Node **Tail, char getdata[1000]);

int main(int argc, char *argv[]) {
    int mytid, tids[PROC];  /* Creates storage for the master process' tid
                               as well as the slave process' tids */
    int no, i, j, who, msgtype; /* no stores the number of processes
                                   actually spawned, i+j are counters, who
                                   is the slave process which has sent the
                                   message, msgtype is the key used to
                                   confirm that information passed between
                                   the master and the slaves is valid */
    int words_found = 0; /* Stores the number of times search_string is
                            found in the file */
    int swords_found; /* Stores the number of times a slave has found a
                         particular search_string */
    int skip_back = 0; /* Stores the amount of overlap there should be
                          between string partitions */
    int working[PROC]; /* Stores whether a particular processor is
                          currently doing work */
    int part_size = 1000; /* Stores the size of the current partition */
    int END_REACHED = 0; /* Set to 1 if the end of the file is reached */
    int DID_RECEIVE; /* Set to 0 if master receives nothing */
    int DONE = 0; /* Set to 1 when the program is over */
    Node *Head, *Tail; /* Head stores the beginning of a queue of strings
                          while Tail stores the end of the queue. Note
                          that Head and Tail are markers, and do not
                          themselves contain any information. */
    char in_data[1000]; /* Stores the data string to be put on the queue */
    char out_data[1000]; /* Stores the data string to be searched */
    char *search_string; /* Holds the string to search for */
    char *filename; /* Holds the name of the file to search */
    FILE *infile; /* Points to the file to be searched */

    mytid = pvm_mytid(); /* Enroll in PVM and set mytid to the tid of the
                            master process */

    /* Check to see if the user has input the correct information in the
       command line */
    if(argc != 3) {
        printf("Usage: cryptomaster <search_string> <filename>\n");
        pvm_exit();
        exit(0);
    }

    /* Open the file to be read from and get the search string, giving an
       error message if the file is unable to be read */
    search_string = argv[1];
    filename = argv[2];
    if((infile = fopen(filename, "r")) == NULL) {
        printf("Error opening '%s'.\n", filename);
        pvm_exit();
        exit(0);
    }

    /* The following attempts to create 10 slave processes, which will run
       the scalc program. The various tids of the slave processes are
       stored in the tids[] array, and the function returns the number of
       slaves actually spawned */

    no = pvm_spawn(SLAVE, (char**)0, 0, "", PROC, tids);    
    if(no < PROC) { /* If the number of processes created is less than the
                       number which should have been created... */
        printf("Error spawning slaves.\n"); /* Print error message */
        for(i - 0; i < no; i++) pvm_kill(tids[i]); /* Close slave
                                                     processes */
        pvm_exit(); /* Close master process */
        exit(0); /* Exit the program */
    }

    /* Initialize the working[] array */
    for(i = 0; i < PROC; i++) {
        working[i] = 0;
    }

    /* Read the initial strings to be processed from the file,
       accounting for an overlap in the data strings. Then, send the
       strings to the slave processes. Strong inspiration drawn from
       Ray Ontko's crytogrep program */
    msgtype = 0;
    for(i = 0; i < PROC; i++) {
        for(j = 0; j <= skip_back; j++) {
            in_data[j] = in_data[part_size-skip_back+j];
        }
        if((part_size = fread(in_data+skip_back, 1, 999-skip_back,
            infile)) == 0) {
            END_REACHED = 1;
            break;
        }
        in_data[part_size+skip_back] = '\0';

        /* Ok, here's where we actually send out the data */
        pvm_initsend(PvmDataDefault);
        pvm_pkint(&DONE, 1, 1);
        pvm_pkint(&i, 1, 1);
        pvm_pkstr(search_string);
        pvm_pkstr(in_data);
        pvm_send(tids[i], msgtype);
        
        working[i] = 1; /* Sets slave's status to working */

        skip_back = strlen(search_string)-1; /* After the first run
                                                through, skip_back will
                                                be set */
    }
    
    /* Ok, now we initialize Head and Tail */
    Head = (Node *)malloc(sizeof(Node));
    Tail = (Node *)malloc(sizeof(Node));
    Head->next = Tail;
    Head->last = NULL;
    Tail->next = NULL;
    Tail->last = Head;

    /* Ok, here we keep a bunch of strings on a queue, and check to see
       if the end of file has been reached. Once the queue is empy
       and the end of file is reached, then the program is over except
       for some cleanup. This also allows the master process to keep
       working, instead of just waiting for data from the slaves. I
       stole this idea straight off of someone in class, Jeremiah I
       believe it was. So, credit to Jeremiah for the idea of using
       a queue. */

    while((!isempty(Head, Tail)) || (!END_REACHED)) {
      /* At this point, if the end of the file has not been reached, the
         master first copies the end of the last string to the beginning
         of the new string, to account for the overlap of search space,
         and then reads in a particular number of characters from the
         input file. */
      if(!END_REACHED) {
        for(j = 0; j <= skip_back; j++) {
            in_data[j] = in_data[part_size-skip_back+j];
        }
        if((part_size = fread(in_data+skip_back, 1, 999-skip_back,
        infile)) == 0) {
            END_REACHED = 1;
        }
        in_data[part_size+skip_back] = '\0';
      }
      /* The data which has just been read is then placed on to the
         queue. */
      if(!END_REACHED) {  /* Remember, this variable could have changed at
                             this point */
        putqueue(&Head, in_data);
      }
      /* Now, assuming the queue isn't empty, the master checks to see if
         any of the slaves are free. If one is, it takes a string from
         the queue and sends it to that slave. */
      if(!isempty(Head, Tail)) {
          for(i = 0; i < PROC; i++) {
              if((!isempty(Head, Tail)) && (!working[i])) {
                  getqueue(&Tail, out_data);
                  msgtype = 0;
                  pvm_initsend(PvmDataDefault);
                  pvm_pkint(&DONE, 1, 1);
                  pvm_pkstr(out_data);
                  pvm_send(tids[i], msgtype);
                  
                  working[i] = 1; /* Once the slave receives the data,
                                     the master sets its state to working
                                     again. */
              }
          }
      }
      /* Assuming there is data from the slave processes to be read, the
         master takes the data and adds it to the number of words found.
         If there is no data waiting, the master moves on and continues
         to place strings on the stack. This adds to time effeciency, as
         this way the master isn't simply sitting around waiting for the
         slaves to process the data. */

      msgtype = 1;
      DID_RECEIVE = pvm_nrecv(-1, msgtype);
      if(DID_RECEIVE > 0) {
          pvm_upkint(&who, 1, 1);
          pvm_upkint(&swords_found, 1, 1);
          words_found += swords_found;
          working[who] = 0; /* Once the slave has sent its data to the
                               master, the master sets it to non-working
                               mode. */
      }
    }
    
    /* This is cleanup. Once the loop is exited, the master has no more
       data to send out. The slaves may still have results to send to the
       master, however. At this point, the master checks to see if there
       are any slaves left working, and if there are, it waits to receive
       their results. */

    msgtype = 1;
    for(i = 0; i < PROC; i++) {
        if(working[i]) {
            pvm_recv(tids[i], msgtype);
            pvm_upkint(&who, 1, 1);
            pvm_upkint(&swords_found, 1, 1);
            words_found += swords_found;
            working[who] = 0;
        }
    }
    DONE = 1;

    /* Now we send the message to the slaves that the program is over,
       which tells the slaves to end their programs. */
    msgtype = 0;
    pvm_initsend(PvmDataDefault);
    pvm_pkint(&DONE, 1, 1);
    pvm_mcast(tids, PROC, msgtype);

    /* Clean up what's left of the queue. */
    free(Head);
    free(Tail);

    /* Print the results. */
    printf("Total occurences of \"%s\": %d\n", search_string,
           words_found);

    /* Close the infile and exit the program. */
    fclose(infile);
    pvm_exit();
    exit(0);
}

/* This creates a new node, sets its data to the input string, and then
   places it at the beginning of the queue. */    
void putqueue(Node **Head, char newdata[1000]) {
    Node *temp;
    temp = (Node *)malloc(sizeof(Node));
    strcpy(temp->data, newdata);
    temp->next = (*Head)->next;
    (*Head)->next->last = temp;
    (*Head)->next = temp;
    temp->last = (*Head);
}

/* This checks to see if the queue is empty. It returns 1 if it is, and 0
   if it is not. */
int isempty(Node *Head, Node *Tail){
    if(Head->next == Tail) return 1;
    else return 0;
}

/* This gets a string from the last node on the queue, and then removes
   that node. */
void getqueue(Node **Tail, char getdata[1000]) {
    Node *temp;

    temp = (*Tail)->last;
    (*Tail)->last = temp->last;
    temp->last->next = (*Tail);
    strcpy(getdata, temp->data);
    free(temp);
}