#include <stdio.h>
#include <stdlib.h>
#include <time.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 N 1000
#define C 4
#define SHMSZ ((N+2)*N+2*C+5) * sizeof(int)
#define VSEMSZ (C*C)
#define EDGEPROB 0.005

typedef int (*matrix)[N];

#define P(s,i) { \
   struct sembuf pop; \
   pop.sem_num = i; \
   pop.sem_op = -1; \
   pop.sem_flg = 0; \
   semop(s, &pop, 1); \
}

#define V(s,i) { \
   struct sembuf vop; \
   vop.sem_num = i; \
   vop.sem_op = 1; \
   vop.sem_flg = 0; \
   semop(s, &vop, 1); \
}

void setup ( int shmid )
{
   matrix G;
   int i, j;
   int *M;

   M = (int *)shmat(shmid, 0, 0);

   /* Number of nodes */
   M[0] = N;
   ++M;

   /* Adjacency matrix */
   G = (matrix)M;
   for (i=0; i<N; ++i) {
      G[i][i] = 0;
      for (j=0; j<i; ++j)
         G[i][j] = G[j][i] = (((double)rand() / (double)RAND_MAX) <= EDGEPROB) ? 1 : 0;
   }
   M += N * N;

   /* Number of processes */
   *M = C;
   ++M;

   /* Number of processes synchronized at current level */
   *M = 0;
   M += 2 * C + 1;

   /* Front and back of Q */
   M[0] = M[1] = 0;
   M += 2;

   /* Initially enqueue vertex 0 */
   M[0] = 0;
   M += N;

   /* All vertices other than vertex 0 is initially unvisited */
   M[0] = 1;
   for (i=1; i<N; ++i) M[i] = 0;

   shmdt(M);
}

void prngraph ( int shmid )
{
   int *M, i, j;
   matrix G;

   printf("\n+++ Input graph\n");
   M = (int *)shmat(shmid, 0, 0);

   G = (matrix)(M+1);
   for (i=0; i<N; ++i) {
      printf("    %4d ->", i);
      for (j=0; j<N; ++j) {
         if (G[i][j]) printf(" %4d", j);
      }
      printf("\n");
   }

   shmdt(M);
   printf("\n");
}

void procchunk ( int i, int shmid, int qsemid, int vsemid, int lssemid, int lesemid )
{
   int *M, *Q, *visited;
   int start, end, u, v, qpos;
   int vsemno;
   int *bfsparent, *bfschild, nadd;
   int B, ndone;
   int (*G)[N];

   M = (int *)shmat(shmid, 0, 0);
   G = (matrix)(M+1);
   Q = M + (N*N+2*C+5);
   visited = Q + N;

   bfsparent = (int *)malloc(N * sizeof(int));
   bfschild = (int *)malloc(N * sizeof(int));

   while (1) {
      P(lssemid,0);
      start = M[N*N+2*i+3];
      end = M[N*N+2*i+4];
      printf("--- Process %d with PID %5d gets Q chunk [%4d,%4d]\n", i, getpid(), start, end);
      if (start < 0) break;
      nadd = 0;
      for (qpos=start; qpos<=end; ++qpos) {
         u = Q[qpos];
         for (v=0; v<N; ++v) {
            if (G[u][v] == 1) {
               vsemno = v % VSEMSZ;
               P(vsemid, vsemno);
               if (!visited[v]) {
                  visited[v] = 1;
                  bfsparent[nadd] = u;
                  bfschild[nadd] = v;
                  ++nadd;
               }
               V(vsemid, vsemno);
            }
         }
      }
      P(qsemid,0);
      for (u=0; u<nadd; ++u) {
         B = ++(M[N*N+2*C+4]);
         Q[B] = bfschild[u];
         printf("    Process %d with PID %5d adds the BFS link (%4d,%4d), and enqueues Q[%4d] = %4d\n",
                     i, getpid(), bfsparent[u], bfschild[u], B, Q[B]);
      }
      ndone = ++(M[N*N+2]);
      V(qsemid,0);
      if (ndone == C) {
         M[N*N+2] = 0;
         V(lesemid,0);
      }
   }

   shmdt(M);
   free(bfsparent);
   free(bfschild);
}

void parbfs ( int shmid, int qsemid, int vsemid, int lssemid, int lesemid )
{
   int i, F, B, start, end, chunksize, l;
   int *M;

   M = (int *)shmat(shmid, 0, 0);

   for (i=0; i<C; ++i) {
      if (!fork()) {
         printf("+++ Child %d with PID %d created\n", i, getpid());
         procchunk(i,shmid,qsemid,vsemid,lssemid,lesemid);
         exit(0);
      }
   }

   l = 1;
   while (1) {
      // sleep(1);
      F = M[N*N+2*C+3]; B = M[N*N+2*C+4];
      if (F > B) {
         printf("\n+++ All reachable nodes are visited. Current Q position is [%4d,%4d].\n\n", F, B);
         for (i=0; i<C; ++i) M[N*N+3+2*i] = -1;
         for (i=0; i<C; ++i) V(lssemid,0);
         break;
      }
      printf("\n+++ Level %d starts. Current Q position is [%4d,%4d].\n", l, F, B);
      chunksize = (B - F + C) / C;
      start = F;
      for (i=0; i<C; ++i) {
         end = start + chunksize - 1;
         if (end > B) end = B;
         M[N*N+3+2*i] = start;
         M[N*N+3+2*i+1] = end;
         start = end + 1;
      }
      M[N*N+2*C+3] = B + 1;
      for (i=0; i<C; ++i) V(lssemid,0);
      P(lesemid,0);
      printf("+++ Level %d ends\n", l);
      ++l;
   }

   for (i=0; i<C; ++i) wait(NULL);

   shmdt(M);
}

int main ( )
{
   int i;
   int shmid, qsemid, vsemid, lssemid, lesemid;

   srand((unsigned int)time(NULL));

   shmid = shmget(IPC_PRIVATE, SHMSZ, 0644 | IPC_CREAT);

   setup(shmid);
   prngraph(shmid);

   qsemid = semget(IPC_PRIVATE, 1, 0644 | IPC_CREAT);
   semctl(qsemid, 0, SETVAL, 1);
   vsemid = semget(IPC_PRIVATE, VSEMSZ, 0644 | IPC_CREAT);
   for (i=0; i<VSEMSZ; ++i) semctl(vsemid, i, SETVAL, 1);
   lssemid = semget(IPC_PRIVATE, 1, 0644 | IPC_CREAT);
   semctl(lssemid, 0, SETVAL, 0);
   lesemid = semget(IPC_PRIVATE, 1, 0644 | IPC_CREAT);
   semctl(lesemid, 0, SETVAL, 0);

   parbfs(shmid, qsemid, vsemid, lssemid, lesemid);

   shmctl(shmid, IPC_RMID, 0);
   semctl(qsemid, 0, IPC_RMID, 0);
   semctl(vsemid, 0, IPC_RMID, 0);
   semctl(lssemid, 0, IPC_RMID, 0);
   semctl(lesemid, 0, IPC_RMID, 0);

   exit(0);
}