// queue.c — cola concurrente con dos locks (Michael y Scott, 1996):
// uno para la cabeza (sacar) y otro para la cola (meter). Un nodo ficticio
// (dummy) separa ambos extremos, así que meter y sacar no se estorban.
//
// P productores meten N números cada uno; P consumidores sacan hasta
// completar P*N. Al final se verifica que la suma coincida.
// Uso:   ./queue [P] [N]
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    long value;
    struct node *next;
} node_t;

typedef struct {
    node_t *head; // nodo ficticio; el primer dato es head->next
    node_t *tail;
    pthread_mutex_t head_lock, tail_lock;
} queue_t;

static void queue_init(queue_t *q) {
    node_t *dummy = malloc(sizeof *dummy);
    if (dummy == NULL)
        exit(1);
    dummy->next = NULL;
    q->head = q->tail = dummy;
    pthread_mutex_init(&q->head_lock, NULL);
    pthread_mutex_init(&q->tail_lock, NULL);
}

static void queue_enqueue(queue_t *q, long value) {
    node_t *n = malloc(sizeof *n);
    if (n == NULL)
        exit(1);
    n->value = value;
    n->next = NULL;
    pthread_mutex_lock(&q->tail_lock);
    // Con la cola vacía, tail es el ficticio y quien saca lee su next sin
    // tail_lock: se publica con release para que vea value ya escrito.
    __atomic_store_n(&q->tail->next, n, __ATOMIC_RELEASE);
    q->tail = n;
    pthread_mutex_unlock(&q->tail_lock);
}

// Devuelve 0 y deja el valor en *value; -1 si la cola está vacía.
static int queue_dequeue(queue_t *q, long *value) {
    pthread_mutex_lock(&q->head_lock);
    node_t *old = q->head;
    node_t *first = __atomic_load_n(&old->next, __ATOMIC_ACQUIRE);
    if (first == NULL) {
        pthread_mutex_unlock(&q->head_lock);
        return -1; // vacía
    }
    *value = first->value;
    q->head = first; // first pasa a ser el nuevo nodo ficticio
    pthread_mutex_unlock(&q->head_lock);
    free(old);
    return 0;
}

static queue_t q;
static long loops;
static long remaining; // cuántos faltan sacar; lo protege count_lock
static pthread_mutex_t count_lock = PTHREAD_MUTEX_INITIALIZER;

static void *producer(void *arg) {
    long id = (long)arg;
    for (long i = 1; i <= loops; i++)
        queue_enqueue(&q, id * loops + i);
    return NULL;
}

static void *consumer(void *arg) {
    long sum = 0, v;
    (void)arg;
    for (;;) {
        pthread_mutex_lock(&count_lock);
        if (remaining == 0) {
            pthread_mutex_unlock(&count_lock);
            break;
        }
        pthread_mutex_unlock(&count_lock);
        if (queue_dequeue(&q, &v) == 0) {
            sum += v;
            pthread_mutex_lock(&count_lock);
            remaining--;
            pthread_mutex_unlock(&count_lock);
        }
        // vacía: volver a intentar (la semana 11 lo arregla con una
        // variable de condición)
    }
    return (void *)sum;
}

int main(int argc, char *argv[]) {
    int p = (argc > 1) ? atoi(argv[1]) : 2;
    loops = (argc > 2) ? atol(argv[2]) : 100000;
    if (p < 1 || p > 32 || loops < 1) {
        fprintf(stderr, "uso: %s [P] [N]\n", argv[0]);
        return 1;
    }
    queue_init(&q);
    remaining = p * loops;

    pthread_t prod[32], cons[32];
    for (long t = 0; t < p; t++) {
        pthread_create(&prod[t], NULL, producer, (void *)t);
        pthread_create(&cons[t], NULL, consumer, NULL);
    }
    long sum = 0;
    for (int t = 0; t < p; t++) {
        void *r;
        pthread_join(prod[t], NULL);
        pthread_join(cons[t], &r);
        sum += (long)r;
    }
    long n = p * loops;
    long expected = n * (n + 1) / 2; // se metieron 1, 2, ..., P*N
    printf("productores=%d consumidores=%d  suma=%ld (esperado %ld) %s\n", p,
           p, sum, expected, sum == expected ? "OK" : "ERROR");
    return 0;
}