//SEMAPHORE

// Process Control Block (Node for Queue)
struct Process
{
    Process* next;
    int* id;
    bool state = true; 
    //  state represents whether the process is blocked or active
    //  true represents active while false represents inactive(blocked)

    //  also other things maybe present here, like the return address, subprocesses, etc
}

//Queue which will allow us to form a FIFO semaphore
//Implementing basic queue functions push() and pop()
struct Queue
{
    Process* front, rear;
    
    int* pop()
    {
        // Underflow
        if(front == NULL)
        {
            return -1;            
        }
        
        else{
            int* val = front->value;
            front = front->next;
            if(front == NULL)
            {
                rear = NULL;
            }
            return val;
        }
    }
    
    void* push(int* val)
    {
        Process* blk = new Process();
        blk->id = val;
        blk->state = false;   
          //  the process is blocked before pushing into the blockedQueue
          //  in reality this is done using system calls
            
        if(rear == NULL)
        {
            front = rear = n;
            
        }
        else
        {
            rear->next = blk;
            rear = blk;
        }
    }
    
}

// Semaphore following FIFO strategy
// structure of the semaphore, as you can see we have linked it to a queue
// this queue would store the list of proessess waiting to acquire the semaphore
struct Semaphore
{
  int value = 1;
  Queue* Q = new Queue();
}
 
//wait()
void wait(Semaphore *S,int* process_id)
{
  S->value--;
  if(S->value < 0)
  {
     S->Q->push(id); 
     //This function will block the proccess until it's woken up.
     //The process will remain in the waiting queue 
     //till it is waken up by the wakeup() system calls
     //This is a type of non-busy waiting
  }
}

//Analogous of wakeup() system call
void wakeup(Process* p) {
    p->state = true;
}
//  In reality, a system call is used instead of this function
//  I have used this function as an analogy of the syscall

//signal()  
void signal(Semaphore *S)
{
  S->value++;
  if(S->value <= 0){
  int* next_process = S->Q->pop();
  wakeup(next_process); 
  //this function will wakeup the process with the given pid using system calls
  }
}

// INITIALIZATION

int read_count = 0;                     
//Variable representing the number of readers 
//currently executing the critical section

Semaphore turn = new Semaphore();        
//Semaphore representing the order in which the writers and 
//readers are requesting access to critical section

Semaphore write_mutex = new Semaphore();         
//Semaphore required to access the critical section
//by the writer for mutual exclusion

Semaphore read_mutex = new Semaphore();     
//Semaphore required to change the read_count variable
//this variable prevents the conflicts while changing the read_count variable
//conflicts might have arose when two readers access the variable simulataneously

//Reader Code 
// this function would be called everytime a new reader arrives

do{
//<ENTRY SECTION>
       wait(turn,process_id);              
       //waiting for its turn to get executed
       
       wait(read_mutex,process_id);           
       //requesting access to change read_count
       
       read_count++;                       
       //update the number of readers trying to access critical section 
       
       // if it is the first reader then request access to critical section
       //requesting  access to the critical section for readers
       if(read_count==1)                   
         wait(write_mutex);
         
       signal(turn);                      
       //releasing turn so that the next reader or writer can take the token
       //and can be serviced
       
       signal(read_mutex);                    
       //release access to the read_count
       
//<CRITICAL SECTION>
       
//<EXIT SECTION>
       wait(read_mutex,process_id)            
       //requesting access to change read_count 
       
       read_count--;                       
       //a reader has finished executing critical section so read_count decrease by 1
       
       //if all the reader have finished executing their critical section
       //releasing access to critical section for next reader or writer
       if(read_count==0)                   
        signal(write_mutex);
        
       signal(read_mutex);                    
       //release access to the read_count  
       
//<REMAINDER SECTION>
       
}while(1);

do{
//<ENTRY SECTION>
      wait(turn,process_id);              
      //waiting for its turn to get executed
      
      wait(write_mutex,process_id);               
      //requesting  access to the critical section
         
//<CRITICAL SECTION>
//Write the data in this "critical section"

//<EXIT SECTION>
      signal(turn,process_id);            
      //releasing turn so that the next reader or writer can take the token
      //and can be serviced
                                       
      signal(write_mutex)                        
      //releasing access to critical section for next reader or writer

//<REMAINDER SECTION>

}while(1);