//=======================================================
// DESIGN-futex-CV.cpp   DRAFT   <mailto:terekhov@web.de>
//=======================================================

#include <cerrno>
#include <cassert>
#include <climits>
#include <pthread.h>

//*** ES aside for a moment...

//*** pthread mutex wrapper
class mutex {

  //*** unimplemented since it's non-copyable/non-copy-constructible
  mutex(const mutex &);
  mutex & operator=(const mutex &);

  pthread_mutex_t m_mutex;

public:

  //*** RAII scoped locking guard
  class guard {

    //*** unimplemented since it's non-copyable/non-copy-constructible
    guard(const guard &);
    guard & operator=(const guard &);

    mutex & m_mutex;

  public:

    guard(mutex & mtx) : m_mutex(mtx) { 
      m_mutex.lock(); 
    }

   ~guard() { 
      m_mutex.unlock(); 
    }

    mutex & mutex_ref() { 
      return m_mutex; 
    }

    pthread_mutex_t & c_mutex_ref() { 
      return m_mutex.c_mutex(); 
    }

  }; //*** class mutex::guard

  //*** RAII scoped "unlocking"/release guard
  class release_guard {

    //*** unimplemented since it's non-copyable/non-copy-constructible
    release_guard(const release_guard &);
    release_guard & operator=(const release_guard &);

    mutex & m_mutex;

  public:

    release_guard(mutex::guard & guard) : m_mutex(guard.mutex_ref()) { 
      m_mutex.unlock(); 
    }

   ~release_guard() { 
      m_mutex.lock(); 
    }

    mutex & mutex_ref() { 
      return m_mutex; 
    }

    pthread_mutex_t & c_mutex_ref() { 
      return m_mutex.c_mutex(); 
    }

  }; //*** class mutex::release_guard

  mutex() {
    int status = pthread_mutex_init(&m_mutex, 0);
    assert(!status);
  }

 ~mutex() {
    int status = pthread_mutex_destroy(&m_mutex);
    assert(!status);
  }

  void lock() {
    int status = pthread_mutex_lock(&m_mutex);
    assert(!status);
  }

  void unlock() {
    int status = pthread_mutex_unlock(&m_mutex);
    assert(!status);
  }

  pthread_mutex_t & c_mutex() { 
    return m_mutex; 
  }

}; //*** class mutex

//*** pthread condvar wrapper
class condvar {

  //*** unimplemented since it's non-copyable/non-copy-constructible
  condvar(const condvar &);
  condvar & operator=(const condvar &);

  pthread_cond_t m_condvar;

public:

  condvar() { 
    int status = pthread_cond_init(&m_condvar, 0);
    assert(!status);
  }

 ~condvar() { 
    int status = pthread_cond_destroy(&m_condvar);
    assert(!status);
  }

  void wait(mutex::guard & guard) {
    int status = pthread_cond_wait(&m_condvar, &guard.c_mutex_ref());
    assert(!status);
  }

  bool timedwait(mutex::guard & guard, const timespec & abstime) {
    int status = pthread_cond_timedwait(
                     &m_condvar, &guard.c_mutex_ref(), &abstime);
    assert(!status || ETIMEDOUT == status);
    return ETIMEDOUT == status;
  }

  void broadcast() {
    int status = pthread_cond_broadcast(&m_condvar);
    assert(!status);
  }

}; //*** class condvar

//*** futex emulator
class futex {

  //*** unimplemented since it's non-copyable/non-copy-constructible
  futex(const futex &);
  futex & operator=(const futex &);

  //*** RAII helper [used inside {timed}wait() only]
  struct waiter {

    waiter(waiter * & queue ) : next(queue), pqueue(&queue) { 
      queue = this; 
    }

   ~waiter() {
      if (!is_reset()) { // timedout/canceled
        while (*pqueue && this != *pqueue) 
          pqueue = &(*pqueue)->next; 
        assert(this == *pqueue);
        *pqueue = next;
      }
    }
            
    waiter * reset() { 
      waiter * w = next; 
      next = this; 
      return w; 
    }

    bool is_reset() { 
      return this == next; 
    }

    waiter *   next;
    waiter * * pqueue;

  } *           m_queue;
  int           m_value;
  mutex mutable m_mutex;
  condvar       m_condvar;
  
public:

  futex() : 
    m_queue(0), m_value(0), m_mutex(), m_condvar() {
  }

 ~futex() { 
    assert(!m_queue); 
  }
 
  operator int() const { 
    mutex::guard guard(m_mutex);
    return m_value; 
  }

  futex & operator=(int value) { 
    mutex::guard guard(m_mutex);
    m_value = value; 
    return *this; 
  }

  futex & operator++() { 
    mutex::guard guard(m_mutex);
    ++m_value; 
    return *this; 
  }

  futex & operator--() { 
    mutex::guard guard(m_mutex);
    --m_value; 
    return *this; 
  }

  // ... other atomic ops ... 

  void wait(int value) {
    mutex::guard guard(m_mutex);
    if (value == m_value) {
      waiter this_waiter(m_queue);
      do { m_condvar.wait(guard); } 
        while (!this_waiter.is_reset());
    }
  }

  bool timedwait(int value, const timespec & abstime, bool & stolen_sig) {
    mutex::guard guard(m_mutex);
    if (value == m_value) {
      waiter this_waiter(m_queue);
      do { 
        if (m_condvar.timedwait(guard, abstime)) {
          // timestamps aside for a moment...
          stolen_sig = this_waiter.is_reset();
          return true; 
        }
      } while (!this_waiter.is_reset());
    }
    return stolen_sig = false;
  }

  void wake(unsigned int wakeups) {
    mutex::guard guard(m_mutex);
    while (m_queue && wakeups--)
      m_queue = m_queue->reset();
    m_condvar.broadcast();
  }

}; //*** class futex

//*** RAII helper
class cancel_off_guard {

  //*** unimplemented since it's non-copyable/non-copy-constructible
  cancel_off_guard(const cancel_off_guard &);
  cancel_off_guard & operator=(const cancel_off_guard &);

  int m_old_cancel_state;

public:

  cancel_off_guard() {
    int status = pthread_setcancelstate(PTHREAD_CANCEL_DISABLE, 
                                        &m_old_cancel_state);
    assert(!status);
  }

 ~cancel_off_guard() {
    int status = pthread_setcancelstate(m_old_cancel_state, 
                                        &m_old_cancel_state);
    assert(!status);
  }

}; //*** class cancel_off_guard

//*** futex-based condvar implementation
class futex_condvar {

  //*** unimplemented since it's non-copyable/non-copy-constructible
  futex_condvar(const futex_condvar &);
  futex_condvar & operator=(const futex_condvar &);

  mutex        m_mutex;
  futex        m_futex;
  unsigned int m_wakeups;  
  unsigned int m_waiters[2];

  //*** Less stress: MIN = INT_MIN and MAX = INT_MAX
  enum CONSTS { MIN = -2, MAX = 1, ALL = UINT_MAX };

  //*** End-Of-Cycle value
  int EOC() const { 
    return (m_futex < 0) ? -1 : MAX; 
  }

  //*** RAII helper [used inside {timed}wait() only]
  struct waiter {

    waiter(futex_condvar * fcv, mutex & mtx) : 
      m_fcv(fcv), m_mtx(mtx), m_ftx(fcv->enter_wait(mtx)), m_sig(true) { 
    }

   ~waiter() { 
      m_fcv->leave_wait(m_ftx, m_sig);
      m_mtx.lock(); 
    }

    int ftx() const { 
      return m_ftx; 
    }

    void no_sig() {
      m_sig = false;
    }

    futex_condvar * m_fcv;
    mutex &         m_mtx;
    int             m_ftx;
    bool            m_sig; // stolen

  }; //*** struct futex_condvar::waiter

  friend struct waiter; // calls enter_wait()/leave_wait()

  int enter_wait(mutex & mtx) {
    mutex::guard guard(m_mutex);
    mtx.unlock();
    ++m_waiters[EOC() == m_futex];
    return m_futex;
  }

  void leave_wait(int ftx, bool stolen_sig) {
    mutex::guard guard(m_mutex);
    if (ftx != m_futex) {
      assert(m_waiters[0]);
      --m_waiters[0];
      if (0 !=   m_wakeups && 
          0 == --m_wakeups && 
          EOC() == m_futex) {
        m_futex = (m_futex < 0) ? 0 : MIN;
        m_waiters[0] = m_wakeups = m_waiters[1];
        m_waiters[1] = 0;
        m_futex.wake(ALL);
        return;
      }
    }
    else {
      --m_waiters[EOC() == ftx];
    }
    if (stolen_sig && m_waiters[0] > m_wakeups) {
      ++m_futex;
      m_wakeups = m_waiters[0];
      m_futex.wake(ALL);
    }
  } 

public:

  futex_condvar() : m_mutex(), m_futex(), m_wakeups(0) {
    m_waiters[0] = m_waiters[1] = 0;
  }

 ~futex_condvar() {
    mutex::guard guard(m_mutex);
    assert(m_waiters[0] == m_wakeups);
    while (m_waiters[0]) {
      int ftx = m_futex = EOC();
      mutex::release_guard release_guard(guard);
      cancel_off_guard no_cancel;
      m_futex.wait(ftx);
    }
  }

  void wait(mutex & mtx) {
    waiter this_waiter(this, mtx);
    m_futex.wait(this_waiter.ftx());
    this_waiter.no_sig();
  }

  bool timedwait(mutex & mtx, const timespec & abstime) {
    waiter this_waiter(this, mtx);
    return m_futex.timedwait(this_waiter.ftx(), abstime, this_waiter.m_sig);
  }

  void signal() {
    unsigned int wakeups;
    {
      mutex::guard guard(m_mutex);
      if (0 != (wakeups = m_waiters[0] > m_wakeups)) {
        if (EOC() == ++m_futex) {
          wakeups = ALL;
          m_wakeups = m_waiters[0];
        }
        else
          ++m_wakeups;
      }
    }
    if (wakeups)
      m_futex.wake(wakeups);
  }

  void broadcast() {
    bool wakeups;
    {
      mutex::guard guard(m_mutex);
      if (false != (wakeups = m_waiters[0] > m_wakeups)) {
        ++m_futex;
        m_wakeups = m_waiters[0];
      }
    }
    if (wakeups)
      m_futex.wake(ALL);
  }
   
}; //*** class futex_condvar

//*** yet another "tennis" (but with futex_condvars this time)
#include <ctime>
#include <iostream>
using namespace std;

enum GAME_STATE {

  START_GAME,
  PLAYER_A,     // Player A plays the ball
  PLAYER_B,     // Player B plays the ball
  GAME_OVER,
  ONE_PLAYER_GONE,
  BOTH_PLAYERS_GONE

}             eGameState;
mutex         mtxGameStateLock;
futex_condvar cndGameStateChange;
futex_condvar cndMainThreadSleep;

const char* id(GAME_STATE ePlayer) {
  assert(PLAYER_A == ePlayer || PLAYER_B == ePlayer);
  return PLAYER_A == ePlayer ? "PLAYER A" : "PLAYER B";
}

GAME_STATE another(GAME_STATE ePlayer) {
  assert(PLAYER_A == ePlayer || PLAYER_B == ePlayer);
  return PLAYER_A == ePlayer ? PLAYER_B : PLAYER_A;
}

extern "C" void * play(void * pPlayer) {
  GAME_STATE ePlayer = *static_cast<GAME_STATE *>(pPlayer);
  mutex::guard guard(mtxGameStateLock);
  while (eGameState < GAME_OVER) {
    cout << id(ePlayer) << "\n";
    eGameState = another(ePlayer);
    cndGameStateChange.signal();
    do { 
      cndGameStateChange.wait(mtxGameStateLock);
      if (another(ePlayer) == eGameState)
        cout << "\n----" << id(ePlayer) << ": SPURIOUS WAKEUP!\n";
    } while (another(ePlayer) == eGameState);
  }
  eGameState = static_cast<GAME_STATE>(eGameState+1);
  cout << id(ePlayer) << " GONE\n";
  cndGameStateChange.broadcast();
  return 0;
}

int main() {
  pthread_t thid;
  eGameState = START_GAME;
  GAME_STATE ePlayerA = PLAYER_A;
  GAME_STATE ePlayerB = PLAYER_B;
  pthread_create(&thid, 0, &play, &ePlayerA);
  pthread_create(&thid, 0, &play, &ePlayerB);
  mutex::guard guard(mtxGameStateLock);
  for (int i = 0; i < 10; ++i) {
    timespec abstime;
    int status = clock_gettime(CLOCK_REALTIME, &abstime);
    assert(!status);
    if (1000000000L <= (abstime.tv_nsec += 100000000L)) {
      abstime.tv_nsec %= 100000000L;
      ++abstime.tv_sec;
    }
    while (!cndMainThreadSleep.timedwait(mtxGameStateLock, abstime)) ;
    cout << "\nMAIN: TIC-TAC [" << 9 - i << "]\n\n";
  }
  eGameState = GAME_OVER;
  cndGameStateChange.broadcast();
  do { cndGameStateChange.wait(mtxGameStateLock); }
    while (BOTH_PLAYERS_GONE != eGameState);
  cout << "\nGAME OVER. Bye-bye.\n";
}