/*
# compilation
$ g++ queue.cpp -O2 -g -pthread -o queue_without_lock -DLOCK_FREE
$ g++ queue.cpp -O2 -g -pthread -o queue_with_lock

# execution time
$ time ./queue_with_lock
real    0m0.035s    0m0.153s    0m0.055s
user    0m0.040s    0m0.270s    0m0.070s
sys     0m0.020s    0m0.030s    0m0.030s

$ time ./queue_without_lock
real    0m0.007s    0m0.007s    0m0.009s
user    0m0.010s    0m0.010s    0m0.010s
sys     0m0.000s    0m0.000s    0m0.000s
*/
#include <cstdio>
#include <pthread.h>
#include <unistd.h>

static const int QUEUE_SIZE = 10;
static const int TEST_ROUND = 100000;

//#define LOCK_FREE

class ScopeLock
{
public:
  ScopeLock(pthread_mutex_t* mutex) : m_mutex(mutex)
  {
    pthread_mutex_lock(mutex);
  }

  ~ScopeLock()
  {
    pthread_mutex_unlock(m_mutex);
  }

private:
  pthread_mutex_t *m_mutex;
};


template <typename T>
class Queue
{
public:
  Queue() : m_head(0)
      , m_tail(0)
  {
#ifndef LOCK_FREE
    pthread_mutexattr_t attr;
    pthread_mutexattr_init(&attr);
    pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_NORMAL);
    pthread_mutex_init(&m_mutex, &attr);
    pthread_mutexattr_destroy(&attr);
#endif
  }

  ~Queue()
  {
  }

  bool append(T val)
  {
#ifndef LOCK_FREE
    ScopeLock lock(&m_mutex);
#endif

    if (is_full()) {
      return false;
    }

    m_data[m_tail] = val;
    m_tail = (m_tail + 1) % QUEUE_SIZE;
    return true;
  }

  bool pop(T* val)
  {
#ifndef LOCK_FREE
    ScopeLock lock(&m_mutex);
#endif

    if (is_empty()) {
      return false;
    }

    *val = m_data[m_head];
    m_head = (m_head + 1) % QUEUE_SIZE;
    return true;
  }

private:
  bool is_full()
  {
    return ((m_tail + 1 + QUEUE_SIZE) % QUEUE_SIZE) == m_head;
  }

  bool is_empty()
  {
    return m_head == m_tail;
  }


#ifdef LOCK_FREE
  volatile int m_head;
  volatile int m_tail;
#else
  int m_head;
  int m_tail;
  pthread_mutex_t m_mutex;
#endif
  T m_data[QUEUE_SIZE];
};


void* producer(void *arg)
{
  Queue<int> *queue = (Queue<int>*)arg;

  for (int i = 1; i <= TEST_ROUND; ) {
    if (queue->append(i)) {
      i++;
    }
  }
  return 0;
}

void consumer(void *arg)
{
  Queue<int> *queue = (Queue<int>*)arg;

  long long sum = 0;
  int val;
  bool result;
  for (int i = 1; i <= TEST_ROUND; i++) {
    do {
      result = queue->pop(&val);
    } while (!result);

    if (i != val) {
      printf("error\n");
      break;
    } else {
      sum += i;
    }
  }
  printf("sum %lld\n", sum);
}

int main(void) {
  pthread_t tid;
  Queue<int> queue;

  pthread_create(&tid, NULL, producer, &queue);
  consumer(&queue);
  pthread_join(tid, NULL);

  return 0;
}