/******************************************************************************
 * Lab Test 2 (Part II only)                                                  *
 * Solution by: Abhijit Das                                                   *
 * Date: October 31, 2008                                                     *
 ******************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <sys/ipc.h>
#include <sys/shm.h>
#include <sys/sem.h>

#define SHMKEY 5555
#define SEMKEY 4444

typedef unsigned long ul;

/* Create the shared memory */
ul *createShm ( ul b )
{
   int shmid;
   ul *mem;

   shmid = shmget(SHMKEY, (b+2)*sizeof(ul), 0777 | IPC_CREAT);
   mem = (ul *)shmat(shmid, 0, 0);
   mem[b] = 0;             /* Size of the divisor list will be stored here */
   mem[b + 1] = (ul)shmid; /* The id is stored here */
   return mem;
}

/* Remove the shared memory */
void deleteShm ( ul *mem, ul b )
{
   int shmid;

   shmid = (int)mem[b+1];  /* Retrieve the shm id */
   shmdt(mem);
   shmctl(shmid, IPC_RMID, 0);
}

/* Create the semaphore and set to the value 1 */
int createSem ()
{
   int semid;

   semid = semget(SEMKEY, 1, 0777 | IPC_CREAT);
   semctl(semid, 0, SETVAL, 1);
   return semid;
}

/* Remove the semaphore */
void deleteSem (int s)
{
   semctl(s, 0, IPC_RMID, 0);
}

#define P(s) semop(s, &pop, 1)
#define V(s) semop(s, &vop, 1)

/* To be executed by child processes */
void searchFactors (ul n, ul lo, ul hi, ul b, ul *mem, int s)
{
   int d;
   struct sembuf pop, vop;

   /* Init sem buffers for P() and V() operaions */
   pop.sem_num = vop.sem_num = 0;
   pop.sem_flg = vop.sem_flg = 0;
   pop.sem_op = -1 ; vop.sem_op = 1;

   srand(lo+hi);
   for (d=lo; d<=hi; ++d) {
      if (n % d == 0) {
         P(s);                   /* Lock access to shared memory */
         mem[mem[b]++] = d;      /* Write divisor */
         V(s);                   /* Unlock access to shared memory */
         usleep(rand() % 1000);  /* Sleep for simulating random insertion */
      }
   }
}

/* To be executed by the parent */
void printFactors (ul *mem, ul b)
{
   ul i, j, k, t;

   k = mem[b]; /* Read the size of the divisor list */

   printf("List of divisors before sorting:\n");
   for (i=0; i<k; ++i) printf("%4lu ", mem[i]);
   printf("\n");

   /* Bubble sort */
   for (j=k-1; j>0; --j) {
      for (i=0; i<j; ++i) {
         if (mem[i] > mem[i+1]) {
            t = mem[i]; mem[i] = mem[i+1]; mem[i+1] = t;
         }
      }
   }

   printf("List of divisors after sorting:\n");
   for (i=0; i<k; ++i) printf("%4lu ", mem[i]);
   printf("\n");
}

int main ()
{
   ul n, b, k, i, t, hi, lo;
   ul *mem;
   int s, status;

   /* Read parameters */
   printf("n = "); scanf("%lu", &n);
   printf("b = "); scanf("%lu", &b);
   printf("k = "); scanf("%lu", &k);

   /* Initialize shared memory and semaphore */
   mem = createShm(b);
   s = createSem();

   t = (b + (k-1)) / k;  /* t is the ceiling of b/k */
   lo = 1; hi = t;       /* The range of search for a child is [lo,hi] */
   for (i=0; i<k; ++i) {
      if (!fork()) {     /* Child process */
         searchFactors(n,lo,hi,b,mem,s);
         exit(0);
      }
      /* Adjust the search range for the next child */
      lo += t; hi += t; if (hi > b) hi = b;
   }

   /* Wait for all of the k child processes to terminate (in any order) */
   for (i=0; i<k; ++i) wait(&status);

   /* Sort the factor list and print */
   printFactors(mem,b);

   /* Remove the shared memory and the semaphore from the system */
   deleteSem(s);
   deleteShm(mem, b);
}