/*
  Aaron Linville
  aaron@linville.org

  Project 3 for CS326

  _VERSION1    Find First
  _VERSION2    Find Worst
  _VERSION3    Find Best
*/

#define _VERSION1

#define TOTAL_CHILDREN 8
#define TOTAL_SHARES 3
#define SHMEM_SIZE 10
#define NUM_REQS 16

#define MSG_TERM 1
#define MSG_MEMREQ 2
#define MSG_RETURN 3

#define MSGPERM 0600
#define SHMPERM 0600

#include <iostream>
#include <sys/errno.h>
#include <sys/ipc.h>
#include <sys/msg.h>
#include <sys/shm.h>
#include <sys/wait.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>

#include <list>
#include <queue>

using namespace std;

struct qtype {
  int mtype;
  int pid;

  int size;
  char *addrptr;
};

struct block {
  char *addr;
  int blockSize;
  bool free;
};

struct pendingReq {
  int reqSize;
  int reqPid;
};

void compacter(list<block>[TOTAL_SHARES], char *);
char *findmem(list<block>[TOTAL_SHARES], int);

void printFreeList(list<block>[TOTAL_SHARES]);
void printFreeMem(char *[TOTAL_SHARES]);

int main(int, char*[]) {
  int pid, msgqid, stat_loc;

  // Shared Memory Vars
  int shmid[TOTAL_SHARES];
  char *shm[TOTAL_SHARES];

  // Message Queue Vars
  int memoryTermRequest, returnMemory, child[TOTAL_CHILDREN];

  // Keys
  key_t key = IPC_PRIVATE;

  // Args to be passed to shmget()
  int size = SHMEM_SIZE;
  int shmflg = IPC_CREAT | IPC_EXCL | SHMPERM;

  // Args to be passed to msgget()
  int msgqflg = IPC_CREAT | IPC_EXCL | MSGPERM;

  // Get shared memory
  for(int i = 0; i < TOTAL_SHARES; i++) {
    if((shmid[i] = shmget(key, size, shmflg)) < 0) {
      cerr << "Unable to get shared memory segement #" << i
           << "! Errno: "
           << errno << endl;
      return 0;
    }
  }

  // Get the message queues used by parent to send to child who
  // requests memory. One queue per child.
  for(int i = 0; i < TOTAL_CHILDREN + 2; i++) {
    // Assign
    if((msgqid = msgget(key, msgqflg)) < 0) {
      cerr << "Unable to get message queue #" << i << "! Errno: "
     << errno << endl;
      return 0;
    } else {
      switch(i) {
      case 0:
        memoryTermRequest = msgqid;
        break;
  
      case 1:
        returnMemory = msgqid;
        break;
  
      default:
        child[i - 2] = msgqid;
        break;
      }
    }
  }
  
  // Fork some children off...
  for(int i = 0; i < TOTAL_CHILDREN; i++) {
    if((pid = fork()) == -1) {
      cerr << "Unable to fork! Errno: " << errno << endl;
      return 0;
    } else if (pid == 0) { // Child
      // Seed the random number generator with pid
      srand(getpid());
      
      // Attach to shared memory...
      for(int j = 0; j < TOTAL_SHARES; j++) {
        if((shm[j] = (char *) shmat(shmid[j], NULL, 0)) == (void *) -1) {
          cerr << "Unable to attach! Errno: "
               << errno << endl;
          return 0;
        }
      }
      
      for(int k = 0; k < NUM_REQS; k++) {
        // Numerical Recipes in C: The Art of Scientific Computing
        // 1st ed, p. 207
        int reqSize = 1 + (int) (10.0 * rand() / (RAND_MAX + 1.0));
        
        char *s;
        
        struct qtype msgReq;
        struct qtype msgRet;
        struct qtype ourMem;
        struct qtype temp;
        
        // Build memory request message
        msgReq.mtype = MSG_MEMREQ;
        msgReq.pid = i;
        msgReq.size = reqSize;
        msgReq.addrptr = 0;
        // Send memory request message
        if(msgsnd(memoryTermRequest, &msgReq, sizeof(struct qtype), 0) < 0) {
          cerr << "CHILD Child " << i
              << " - Error sending request message! Errno: " << errno << endl;
        }
        
        ourMem.mtype = 0;
        ourMem.pid = 0;
        ourMem.size = 0;
        ourMem.addrptr = 0;
        // Wait for memory
        if(msgrcv(child[i], &ourMem, sizeof(struct qtype), 0, 0) < 0) {
          cerr << "CHILD Child " << i
          << " - Error waiting on message! Errno: " << errno << endl;
        }
        
        temp = ourMem;
        s = temp.addrptr;
        
        // Fill our seg with the num of th size
        for(int j = 0; j < temp.size; j++) {
          *s++ = temp.size;
        }
        
        // Build memory return message
        msgRet.mtype = MSG_RETURN;
        msgRet.pid = i;
        msgRet.size = reqSize;
        msgRet.addrptr = temp.addrptr;
        // Send memory return message
        if(msgsnd(returnMemory, &msgRet, sizeof(struct qtype), 0) < 0) {
          cerr << "CHILD Child " << i
               << " - Error sending message! Errno: " << errno << endl;
        }
      }
      
      struct qtype msgTerm;
      
      // Build termination message
      msgTerm.mtype = MSG_TERM;
      msgTerm.pid = i;
      msgTerm.size = 0;
      msgTerm.addrptr = 0;
      // Send termination message
      if(msgsnd(memoryTermRequest, &msgTerm, sizeof(struct qtype), 0) < 0) {
        cerr << "CHILD Child " << i
             << "Error sending message! Errno: " << errno << endl;
      }
      
      return 0;
    }
  } // for() - Forks children off

  //
  // Parent
  //

  // Attach to shared memory...
  for(int i = 0; i < TOTAL_SHARES; i++) {
    if((shm[i] = (char *) shmat(shmid[i], NULL, 0)) == (void *) -1) {
      cerr << "Parent unable to attach! Errno: "
           << errno << endl;
      return 0;
    }
  }

  int termCnt = 0;

  /*
    Wasting important CPU power trying to find free space
    when the memory state hasn't changed sinced the last
    time we checked is bad. So if you can't find space the
    first time you check, wait until memory changes!!!
  */
  bool memChng = false;
  bool memWait = false;
  
  queue<pendingReq> pendingRequests;
  list<block> memSeg[TOTAL_SHARES];

  struct qtype childMemReq;
  struct qtype childMemRet;
  struct qtype tempqtype;

  block tempBlock;
  
  for(int i = 0; i < TOTAL_SHARES; i++) {
    tempBlock.addr = shm[i];
    tempBlock.blockSize = SHMEM_SIZE;
    tempBlock.free = true;

    memSeg[i].push_back(tempBlock);
  }

  // Event loop
  while(termCnt < TOTAL_CHILDREN) {
    // Child termination, memory request
    if(msgrcv(memoryTermRequest, &childMemReq, sizeof(struct qtype), 0, IPC_NOWAIT) >= 0) {
      tempqtype = childMemReq;

      switch(tempqtype.mtype) {
      case MSG_TERM:
        cout << "PARNT Child " << tempqtype.pid
             << " has informed me of its termination." << endl;
        termCnt++;
        break;
  
      case MSG_MEMREQ:
        cout << "PARNT Child " << tempqtype.pid
             << " requested " << tempqtype.size
             << " blocks." << endl;
  
        pendingReq temp;
          
        temp.reqSize = tempqtype.size;
        temp.reqPid = tempqtype.pid;
          
        pendingRequests.push(temp);
        break;
  
      default:
        cerr << "Unknown memory request!" << endl;
        break;
      } //switch(memory type)
    } //if(memoryTermRequest)

    // Child memory return
    if(msgrcv(returnMemory, &childMemRet, sizeof(struct qtype), 0, IPC_NOWAIT) >= 0) {
      tempqtype = childMemRet;

      switch(tempqtype.mtype) {
      case MSG_RETURN:
        // find corresponding address
        cout << "PARNT Child " << tempqtype.pid << " returns "
             << tempqtype.size << " blocks memory." << endl;
        memChng = true;

        compacter(memSeg, tempqtype.addrptr);

        cout << "Memory state after return: " << endl;
        printFreeList(memSeg);
        break;
        
      default:
        cerr << "Unknown memory return!" << endl;
        break;
      } // switch(return type) 
    } // if(returnMemory)
    
    // Allocation of memory
    if(!(memWait == true && memChng == false)) {
      if(pendingRequests.empty() == false) {
        struct qtype childMemSnd;
        
        childMemSnd.size = pendingRequests.front().reqSize;
        char *temp;
        
        if((temp = findmem(memSeg, childMemSnd.size)) != 0) {
          childMemSnd.addrptr = temp;
          
          // Let the child know of its memory we have allocated for it
          if(msgsnd(child[pendingRequests.front().reqPid], &childMemSnd, sizeof(struct qtype), 0) < 0)
            cerr << "Error sending child " << pendingRequests.front().reqPid
                 <<  " its memory request! Errno: " << errno << endl;
          pendingRequests.pop();
          
          cout << "Memory state after allocation: " << endl;
          printFreeList(memSeg);
          
          memWait = false;
        } else {
          // Memory wasn't found. Make sure we don't check
          // check until the memory state has changed.
          memChng = false;
          memWait = true;
        }
      }// if(Pending Requests)
    }
  } // while(termCnt < TOTAL_CHILDREN)
  
  // Wait for the children to die
  for(int i = 0; i < TOTAL_CHILDREN; i++) {
    wait(&stat_loc);
  }

  // Destroy all the queues
  for(int i = 0; i < TOTAL_CHILDREN + 2; i++) {
    switch(i) {
    case 0:
      msgqid = memoryTermRequest;
      break;

    case 1:
      msgqid = returnMemory;
      break;

    default:
      msgqid = child[i - 2];
      break;
    }
    
    if(msgctl(msgqid, IPC_RMID, NULL) == -1) {
      cerr << "Unable to destroy message queue #" << i << "! Errno "
           << errno << endl;
    }
  }
  
  // Destroy shared memory
  for(int i = 0; i < TOTAL_SHARES; i++) {
    if(shmctl(shmid[i], IPC_RMID, NULL) < 0) {
      cerr << "Unable to destroy shared memory segement #" << i
           << "! Errno: " << errno << endl;
    }
  }

  // We made it!
  return 0;
}

/*
  Outputs the list of what memory is being used and what not.
*/
void printFreeList(list<block> memSeg[TOTAL_SHARES]) {
  for(int i = 0; i < TOTAL_SHARES; i++) {
    cout << "Memory Segement " << i << endl;
    
    list<block>::iterator j;
    int k = 0;
    int lastPos = 0;
    for(j = memSeg[i].begin(); j != memSeg[i].end(); j++) {
      cout << "Block: " << ++k << " " << lastPos;
      
      if((lastPos + (*j).blockSize - 1) != lastPos) {
        cout << "-" << (lastPos + (*j).blockSize - 1) << " are ";
      } else {
        cout << " is ";
      }
      
      ((*j).free == 0)?cout << "used":cout << "free";
      cout << "." << endl;
      
      lastPos += (*j).blockSize;
    }
  }
  
  return;
}

/*
  Outputs the contents of shared memory to the console.
*/
void printFreeMem(char *shm[TOTAL_SHARES]) {
  char *s;

  for(int i = 0; i < TOTAL_SHARES; i++) {
    cout << "Memory Segment " << i << " - ";

    s = shm[i];
    for(int j = 0; j < SHMEM_SIZE; j++) {
      cout << int(*s++) << " ";
    }
    cout << endl;
  }

  return;
}

#ifdef _VERSION1
// First Fit
char *findmem(list<block> memSeg[TOTAL_SHARES], int size) {
  block temp;
  char *tempAddr;
  
  for(int i = 0; i < TOTAL_SHARES; i++) {
    list<block>::iterator j;
    for(j = memSeg[i].begin(); j != memSeg[i].end(); j++) {
      if((*j).free == true &&
         (*j).blockSize >= size) {
        
        temp.blockSize = size;
        temp.free = false;
        temp.addr = tempAddr = (*j).addr;
        memSeg[i].insert(j, temp);
        
        if((*j).blockSize > size) {
          temp.blockSize = (*j).blockSize - size;
          temp.free = true;
          temp.addr = (*j).addr + (char) size;
          memSeg[i].insert(j, temp);
        }
        
        memSeg[i].erase(j);
        
        return tempAddr;
      }
    } // for each memseg
  } // for total shares 
  
  return 0;
}
#endif

#ifdef _VERSION2
// Worst Fit
char *findmem(list<block> memSeg[TOTAL_SHARES], int size) {
  list<block>::iterator lastNode;
  int lastSize = 0;
  int lastBlock = 0;
  block temp;
  char *tempAddr;
  
  for(int i = 0; i < TOTAL_SHARES; i++) {
    list<block>::iterator j;
    for(j = memSeg[i].begin(); j != memSeg[i].end(); j++) {
      if((*j).free == true &&
         (*j).blockSize >= size &&
         (*j).blockSize > lastSize) {
        lastNode = j;
        lastBlock = i;
        if((lastSize = (*j).blockSize) == SHMEM_SIZE) {
          goto evil; // bad programmer, no cookie.
        }
      }
    } // for each memseg
  } // for total shares
  
evil:
  
  if(lastSize != 0) {
    temp.blockSize = size;
    temp.free = false;
    temp.addr = tempAddr = (*lastNode).addr;
    memSeg[lastBlock].insert(lastNode, temp);
    
    if((*lastNode).blockSize != size) {    
      temp.blockSize = (*lastNode).blockSize - size;
      temp.free = true;
      temp.addr = (*lastNode).addr + (char) size;
      memSeg[lastBlock].insert(lastNode, temp);
    }      
    
    memSeg[lastBlock].erase(lastNode);
    
    return tempAddr;
  } else {
    return 0;
  }
}
#endif

#ifdef _VERSION3
// Best Fit
char *findmem(list<block> memSeg[TOTAL_SHARES], int size) {
  list<block>::iterator lastNode;
  int lastSize = SHMEM_SIZE + 1;
  int lastBlock = 0;
  block temp;
  char *tempAddr;
  
  for(int i = 0; i < TOTAL_SHARES; i++) {
    list<block>::iterator j;
    for(j = memSeg[i].begin(); j != memSeg[i].end(); j++) {
      if((*j).free == true &&
         (*j).blockSize >= size &&
         (*j).blockSize < lastSize) {
        lastSize = (*j).blockSize;
        lastNode = j;
        lastBlock = i;
        
        if((*j).blockSize == size) {
          goto evil; // bad progammer, no cookie
        }
      }
    }
  }
  
evil:
  if(lastSize != (SHMEM_SIZE + 1)) {
    temp.blockSize = size;
    temp.free = false;
    temp.addr = tempAddr = (*lastNode).addr;
    memSeg[lastBlock].insert(lastNode, temp);
    
    if((*lastNode).blockSize != size) {
      temp.blockSize = (*lastNode).blockSize - size;
      temp.free = true;
      temp.addr = (*lastNode).addr + (char) size;
      memSeg[lastBlock].insert(lastNode, temp);
    }
    
    memSeg[lastBlock].erase(lastNode);
    
    return tempAddr;
  } else {
    return 0;
  }
}
#endif

/*
  Send it an address, it will attempt to locate the start
  of a block of memory and then mark it as unused. Then
  it will procede to try and join itself to free memory
  around itself (if there is any)
*/
void compacter(list<block> memSeg[TOTAL_SHARES], char *retAddr) {
  list<block>::iterator j;
  list<block>::iterator k;
  
  for(int i = 0; i < TOTAL_SHARES; i++) {
    for(j = memSeg[i].begin(); j != memSeg[i].end(); j++) {
      if((*j).addr == retAddr) {
         (*j).free = true;
        
        // Check next block, if it is free, compact!
        k = j;
        k++;
        if((j != memSeg[i].end()) &&
           ((*k).free == true)) {
          (*j).blockSize += (*k).blockSize;
          memSeg[i].erase(k);
        }
        
        // Check previous block, if it is free, compact!
        k = j;
        k--;
        if((j != memSeg[i].begin() &&
            (*k).free == true)) {
          (*j).addr = (*k).addr;
          (*j).blockSize += (*k).blockSize;
          memSeg[i].erase(k);
        }
        
        return;
      } // if(iter.addr = addr)
    } // for each memseg
  } // for total shares
  
  cerr << "Unable to free memory!" << endl;
  return;
}