#include <iostream>
#include <pthread.h>
#include <sys/time.h>
#include <errno.h>

using namespace std;

const bool releaseMutexBetweenSignals = true;
const int waitTimeSec = 15;

bool exitProgram;
int threadsCount;
int waitingCount;
int signalsSentCount;
int secondWaitingCount;
int secondWaitWokenCount;
pthread_mutex_t mutex;
pthread_cond_t testCond;
pthread_cond_t allThreadsWaiting;
pthread_cond_t allSignalsSent;
pthread_cond_t allThreadsUnblocked;
pthread_cond_t twoOrAllAtSecondWait;

void* ThreadMain(void* data)
{
    // Wait for all threds to be created.
    pthread_mutex_lock(&mutex);
    while (!exitProgram) {
    // 1. Wait on the condition for the first time. Count the waiters at this step
        // 1.1. If all threads are blocked at the first wait, signal the master thread
        if (++waitingCount == threadsCount) {
            pthread_cond_signal(&allThreadsWaiting);
        }

        // 1.2. Wait on the condition for the first time.
        pthread_cond_wait(&testCond, &mutex);

        // 1.3. Decrement the number of waiting threads
        if (--waitingCount == 0) {
            pthread_cond_signal(&allThreadsUnblocked);
        }

        if (exitProgram) {
            break;
        }

    // 2. Wait on the condition for the second time. Count waiters at this step too
        // 2.1. Don't start waiting until the main thread has sent all signals
        while (signalsSentCount < threadsCount && !exitProgram) {
            pthread_cond_wait(&allSignalsSent, &mutex);
        }

        if (exitProgram) {
            break;
        }

        // 2.2. When there are two threads blocked on the second wait inform the main
        //      thread to send one more signal. When all threads have reached the second
        //      wait, signal the same condition to inform the main thread that it can
        //      initiate the next test iteration.
        if (++secondWaitingCount == 2 || secondWaitingCount == threadsCount) {
            pthread_cond_signal(&twoOrAllAtSecondWait);
        }

        // 2.3. Wait on the condition for the second time
        pthread_cond_wait(&testCond, &mutex);
        ++secondWaitWokenCount;

        if (exitProgram) {
            break;
        }

    // 3. Wait for the test iteration to end
        while (signalsSentCount > 0 && !exitProgram) {
            pthread_cond_wait(&testCond, &mutex);
        }

        if (exitProgram) {
            break;
        }
   }
    pthread_mutex_unlock(&mutex);
    pthread_exit(NULL);
}

int main()
{
// 1. Test setup:
    // 1.1. Initialize the mutex and the condition variables
    pthread_mutex_init(&mutex, NULL);
    pthread_cond_init(&allThreadsWaiting, NULL);
    pthread_cond_init(&testCond, NULL);
    pthread_cond_init(&allSignalsSent, NULL);
    pthread_cond_init(&allThreadsUnblocked, NULL);
    pthread_cond_init(&twoOrAllAtSecondWait, NULL);

    // 1.2. Create as many threads as possible. All created threads will imediately
    //      block on the mutex
    pthread_mutex_lock(&mutex);
    exitProgram = false;

    for (threadsCount = 0; ; ++threadsCount) {
        pthread_t thread;

        if (pthread_create(&thread, NULL, ThreadMain, NULL) != 0) {
            break;
        }

        pthread_detach(thread);
    }

    cout << "Created " << threadsCount << " threads." << endl;

// 2. Test body
    while (!exitProgram) {
        // 2.1. Release the mutex and start waiting for all threads to block on the
        //      condition variable
        waitingCount = 0;
        signalsSentCount = 0;

        while (waitingCount < threadsCount) {
            pthread_cond_wait(&allThreadsWaiting, &mutex);
        }

        // 2.2. Unblock all threads but use individual signals instead of broadcast
        secondWaitingCount = 0;
        secondWaitWokenCount = 0;

        for (signalsSentCount = 0; signalsSentCount < threadsCount; ++signalsSentCount) {
            pthread_cond_signal(&testCond);

            if (releaseMutexBetweenSignals) {
                pthread_mutex_unlock(&mutex);
                pthread_mutex_lock(&mutex);
            }
        }

        // 2.3. Send a broadcast on the allSignalsSent condition in case there are
        //      threads that were unblocked from the first wait and are waiting to
        //      enter the second wait
        pthread_cond_broadcast(&allSignalsSent);

        // 2.3. Wait for at least two threads to be blocked on the second wait
        while (secondWaitingCount < 2) {
            pthread_cond_wait(&twoOrAllAtSecondWait, &mutex);
        }

        // 2.4. Send a single signal
        pthread_cond_signal(&testCond);

        // 2.5. Wait for all threads to move beyond the first wait
        struct timeval currentTime;
                struct timespec endTime;

        gettimeofday(&currentTime, NULL);
        endTime.tv_sec = currentTime.tv_sec;
        endTime.tv_nsec = currentTime.tv_usec * 1000;
        endTime.tv_sec += waitTimeSec;

        while (waitingCount > 0) {
            if (pthread_cond_timedwait(&allThreadsUnblocked, &mutex, &endTime) ==
                                                                            ETIMEDOUT) {
                break;
            }
        }

        // 2.6. If some threads are still blocked on the first wait, we have
        //      reproduced the problem. End the test.
        if (waitingCount > 0 ){
            cout << "After " << waitTimeSec << " seconds " << waitingCount
                 << " threads are still blocked on the first wait and "
                 << secondWaitWokenCount << " threads have woken from the second wait"
                 << endl;
            exitProgram = true;
            // Let all threads move to the second wait
            pthread_cond_broadcast(&testCond);
            // Exit the test iterations loop
            break;
        } else {
            cout << "All threads were unblocked." << endl;
        }

        // 2.7. Wait for all threads to reach the second wait.
        while (secondWaitingCount < threadsCount) {
            pthread_cond_wait(&twoOrAllAtSecondWait, &mutex);
        }

        // 2.8. Send a broadcast to let all threads move to the start of the next
        //      test iteration
        pthread_cond_broadcast(&testCond);
    }

    pthread_mutex_unlock(&mutex);
    pthread_exit(NULL);
}