// hash.c — tabla hash concurrente: un lock global vs. un lock por bucket.
//
// Cada hilo inserta N claves distintas y luego las busca todas.
// Con un lock global los hilos se turnan; con un lock por bucket solo
// chocan si dos hilos tocan el mismo bucket a la vez.
//
// Uso:   ./hash global|bucket HILOS [N]
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define BUCKETS 1024
#define MAXT 64

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

// Una lista enlazada con su propio lock (OSTEP fig. 29.8).
typedef struct {
    node_t *head;
    pthread_mutex_t lock;
} list_t;

typedef struct {
    list_t bucket[BUCKETS];
    pthread_mutex_t global; // solo se usa en modo global
    int per_bucket;         // 1: lock por bucket; 0: lock global
} hash_t;

static void list_init(list_t *l) {
    l->head = NULL;
    pthread_mutex_init(&l->lock, NULL);
}

// Insertar al inicio. malloc va FUERA del lock: no necesita protección.
static int list_insert(list_t *l, long key, int use_lock) {
    node_t *n = malloc(sizeof *n);
    if (n == NULL)
        return -1;
    n->key = key;
    if (use_lock)
        pthread_mutex_lock(&l->lock);
    n->next = l->head;
    l->head = n;
    if (use_lock)
        pthread_mutex_unlock(&l->lock);
    return 0;
}

static int list_lookup(list_t *l, long key, int use_lock) {
    int found = 0;
    if (use_lock)
        pthread_mutex_lock(&l->lock);
    for (node_t *p = l->head; p != NULL; p = p->next)
        if (p->key == key) {
            found = 1;
            break; // un solo camino de salida: el unlock no se olvida
        }
    if (use_lock)
        pthread_mutex_unlock(&l->lock);
    return found;
}

static void hash_init(hash_t *h, int per_bucket) {
    for (int i = 0; i < BUCKETS; i++)
        list_init(&h->bucket[i]);
    pthread_mutex_init(&h->global, NULL);
    h->per_bucket = per_bucket;
}

static list_t *hash_bucket(hash_t *h, long key) {
    unsigned long x = (unsigned long)key * 0x9E3779B97F4A7C15UL; // mezclar
    return &h->bucket[x >> 54]; // 10 bits altos: 0..1023
}

static int hash_insert(hash_t *h, long key) {
    if (h->per_bucket)
        return list_insert(hash_bucket(h, key), key, 1);
    pthread_mutex_lock(&h->global);
    int rc = list_insert(hash_bucket(h, key), key, 0);
    pthread_mutex_unlock(&h->global);
    return rc;
}

static int hash_lookup(hash_t *h, long key) {
    if (h->per_bucket)
        return list_lookup(hash_bucket(h, key), key, 1);
    pthread_mutex_lock(&h->global);
    int rc = list_lookup(hash_bucket(h, key), key, 0);
    pthread_mutex_unlock(&h->global);
    return rc;
}

static hash_t table;
static long loops;
static long found[MAXT];

static void *worker(void *arg) {
    long id = (long)arg;
    for (long i = 0; i < loops; i++)
        hash_insert(&table, id * loops + i);
    for (long i = 0; i < loops; i++)
        found[id] += hash_lookup(&table, id * loops + i);
    return NULL;
}

int main(int argc, char *argv[]) {
    if (argc < 3) {
        fprintf(stderr, "uso: %s global|bucket HILOS [N]\n", argv[0]);
        return 1;
    }
    int per_bucket = strcmp(argv[1], "bucket") == 0;
    int nthreads = atoi(argv[2]);
    loops = (argc > 3) ? atol(argv[3]) : 20000;
    if (nthreads < 1 || nthreads > MAXT || loops < 1) {
        fprintf(stderr, "argumentos inválidos\n");
        return 1;
    }
    hash_init(&table, per_bucket);

    struct timespec a, b;
    pthread_t th[MAXT];
    clock_gettime(CLOCK_MONOTONIC, &a);
    for (long t = 0; t < nthreads; t++)
        pthread_create(&th[t], NULL, worker, (void *)t);
    for (int t = 0; t < nthreads; t++)
        pthread_join(th[t], NULL);
    clock_gettime(CLOCK_MONOTONIC, &b);

    long total = 0, size = 0;
    for (int t = 0; t < nthreads; t++)
        total += found[t];
    for (int i = 0; i < BUCKETS; i++)
        for (node_t *p = table.bucket[i].head; p != NULL; p = p->next)
            size++;
    double dt = (b.tv_sec - a.tv_sec) + (b.tv_nsec - a.tv_nsec) / 1e9;
    printf("%-6s hilos=%d  %.3f s  elementos=%ld  encontrados=%ld (esperado "
           "%ld)\n",
           argv[1], nthreads, dt, size, total, nthreads * loops);
    return 0;
}

// list.c — lista enlazada concurrente: un lock para toda la lista vs.
// hand-over-hand (un lock por nodo, se toma el siguiente antes de soltar
// el actual).
//
// Se arma una lista de M nodos y cada hilo hace B búsquedas.
// Uso:   ./list uno|hoh HILOS [M] [B]
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

typedef struct node {
    long key;
    struct node *next;
    pthread_mutex_t lock; // solo para hand-over-hand
} node_t;

typedef struct {
    node_t *head;
    pthread_mutex_t lock; // lock de la lista (o de la cabeza, en hoh)
} list_t;

static list_t list;
static int hoh; // 1: hand-over-hand
static long nodes, lookups;

static void list_insert(long key) {
    node_t *n = malloc(sizeof *n);
    if (n == NULL)
        exit(1);
    n->key = key;
    pthread_mutex_init(&n->lock, NULL);
    pthread_mutex_lock(&list.lock); // en ambos modos, la cabeza la cuida list.lock
    n->next = list.head;
    list.head = n;
    pthread_mutex_unlock(&list.lock);
}

static int lookup_one_lock(long key) {
    int found = 0;
    pthread_mutex_lock(&list.lock);
    for (node_t *p = list.head; p != NULL; p = p->next)
        if (p->key == key) {
            found = 1;
            break;
        }
    pthread_mutex_unlock(&list.lock);
    return found;
}

static int lookup_hoh(long key) {
    pthread_mutex_lock(&list.lock);
    node_t *p = list.head;
    if (p == NULL) {
        pthread_mutex_unlock(&list.lock);
        return 0;
    }
    pthread_mutex_lock(&p->lock); // tomar el primer nodo...
    pthread_mutex_unlock(&list.lock); // ...y recién soltar la cabeza
    while (p != NULL) {
        if (p->key == key) {
            pthread_mutex_unlock(&p->lock);
            return 1;
        }
        node_t *next = p->next;
        if (next != NULL)
            pthread_mutex_lock(&next->lock); // mano siguiente
        pthread_mutex_unlock(&p->lock);      // soltar la anterior
        p = next;
    }
    return 0;
}

static void *worker(void *arg) {
    unsigned seed = (unsigned)(long)arg + 1;
    long hits = 0;
    for (long i = 0; i < lookups; i++) {
        long key = rand_r(&seed) % nodes;
        hits += hoh ? lookup_hoh(key) : lookup_one_lock(key);
    }
    return (void *)hits;
}

int main(int argc, char *argv[]) {
    if (argc < 3) {
        fprintf(stderr, "uso: %s uno|hoh HILOS [M] [B]\n", argv[0]);
        return 1;
    }
    hoh = strcmp(argv[1], "hoh") == 0;
    int nthreads = atoi(argv[2]);
    nodes = (argc > 3) ? atol(argv[3]) : 1000;
    lookups = (argc > 4) ? atol(argv[4]) : 20000;
    if (nthreads < 1 || nthreads > 64 || nodes < 1 || lookups < 1) {
        fprintf(stderr, "argumentos inválidos\n");
        return 1;
    }
    pthread_mutex_init(&list.lock, NULL);
    for (long k = 0; k < nodes; k++)
        list_insert(k);

    pthread_t th[64];
    struct timespec a, b;
    clock_gettime(CLOCK_MONOTONIC, &a);
    for (long t = 0; t < nthreads; t++)
        pthread_create(&th[t], NULL, worker, (void *)t);
    long hits = 0;
    for (int t = 0; t < nthreads; t++) {
        void *r;
        pthread_join(th[t], &r);
        hits += (long)r;
    }
    clock_gettime(CLOCK_MONOTONIC, &b);
    double dt = (b.tv_sec - a.tv_sec) + (b.tv_nsec - a.tv_nsec) / 1e9;
    printf("%-3s hilos=%d  M=%ld  %.3f s  encontrados=%ld de %ld\n", argv[1],
           nthreads, nodes, dt, hits, nthreads * lookups);
    return 0;
}

// locks.h — tres locks hechos a mano con atómicos de C11 (<stdatomic.h>):
//
//   tas_lock     spinlock con test-and-set (atomic_exchange)
//   ticket_lock  ticket lock con fetch-and-add: atiende en orden de llegada
//   futex_lock   lock de dos fases: gira un rato y luego duerme con futex
//
// Todo vive en el header (funciones static inline) para que el compilador
// pueda integrarlas en el lazo del benchmark.
#ifndef LOCKS_H
#define LOCKS_H

#include <linux/futex.h>
#include <sched.h>
#include <stdatomic.h>
#include <sys/syscall.h>
#include <unistd.h>

// Pista para el procesador: "estoy girando". No cambia la semántica.
static inline void cpu_relax(void) {
#if defined(__aarch64__)
    __asm__ __volatile__("yield");
#elif defined(__x86_64__)
    __asm__ __volatile__("pause");
#endif
}

// ------------------------------------------------------------
// Spinlock con test-and-set
// ------------------------------------------------------------
typedef struct {
    atomic_int locked; // 0 libre, 1 tomado
} tas_lock;

static inline void tas_init(tas_lock *l) { atomic_init(&l->locked, 0); }

static inline void tas_acquire(tas_lock *l) {
    // TestAndSet: escribe 1 y devuelve el valor anterior, en un solo paso.
    while (atomic_exchange_explicit(&l->locked, 1, memory_order_acquire) == 1)
        cpu_relax();
}

// Variante que cede la CPU en vez de girar (OSTEP 28.13).
static inline void tas_acquire_yield(tas_lock *l) {
    while (atomic_exchange_explicit(&l->locked, 1, memory_order_acquire) == 1)
        sched_yield();
}

static inline void tas_release(tas_lock *l) {
    atomic_store_explicit(&l->locked, 0, memory_order_release);
}

// ------------------------------------------------------------
// Ticket lock con fetch-and-add
// ------------------------------------------------------------
typedef struct {
    atomic_uint ticket; // siguiente número a repartir
    atomic_uint turn;   // número que se atiende ahora
} ticket_lock;

static inline void ticket_init(ticket_lock *l) {
    atomic_init(&l->ticket, 0);
    atomic_init(&l->turn, 0);
}

static inline void ticket_acquire(ticket_lock *l) {
    unsigned my = atomic_fetch_add_explicit(&l->ticket, 1, memory_order_relaxed);
    while (atomic_load_explicit(&l->turn, memory_order_acquire) != my)
        cpu_relax();
}

static inline void ticket_release(ticket_lock *l) {
    // Solo el owner escribe turn, pero se usa fetch_add por claridad.
    atomic_fetch_add_explicit(&l->turn, 1, memory_order_release);
}

// ------------------------------------------------------------
// Lock de dos fases con futex (estilo glibc, 3 estados)
//   0 = libre, 1 = tomado sin esperas, 2 = tomado y quizá hay quien duerme
// ------------------------------------------------------------
typedef struct {
    atomic_int state;
} futex_lock;

#define FUTEX_SPINS 100 // fase 1: cuántas veces girar antes de dormir

static inline long sys_futex(atomic_int *addr, int op, int val) {
    return syscall(SYS_futex, addr, op, val, NULL, NULL, 0);
}

static inline void futex_init(futex_lock *l) { atomic_init(&l->state, 0); }

static inline void futex_acquire(futex_lock *l) {
    int c = 0;
    // Camino rápido: 0 -> 1 sin entrar al kernel.
    if (atomic_compare_exchange_strong(&l->state, &c, 1))
        return;
    // Fase 1: girar un poco, por si el owner suelta pronto.
    for (int i = 0; i < FUTEX_SPINS; i++) {
        c = 0;
        if (atomic_compare_exchange_strong(&l->state, &c, 1))
            return;
        cpu_relax();
    }
    // Fase 2: marcar "hay esperas" (2) y dormir mientras siga tomado.
    while (atomic_exchange(&l->state, 2) != 0)
        sys_futex(&l->state, FUTEX_WAIT_PRIVATE, 2); // duerme si state == 2
}

static inline void futex_release(futex_lock *l) {
    // Si nadie esperaba (estaba en 1), no hace falta llamar al kernel.
    if (atomic_exchange(&l->state, 0) == 2)
        sys_futex(&l->state, FUTEX_WAKE_PRIVATE, 1); // despierta a uno
}

#endif

// peterson.c — dos locks hechos solo con loads y stores, y por qué fallan.
//
// Dos hilos suman N veces cada uno a un contador, dentro de un lock:
//   flag      lock con una bandera: "mirar y luego tomar" (roto siempre)
//   peterson  algoritmo de Peterson sin barreras de memoria
//   fence     Peterson con una barrera (fence) entre escribir y leer
//
// En un procesador con memoria débil (ARM, RISC-V) o con store buffer (x86)
// el modo peterson también pierde sumas: la escritura de flag[yo] puede
// quedar en el store buffer mientras se lee flag[otro].
//
// Uso:  ./peterson flag|peterson|fence [N]
#include <pthread.h>
#include <stdatomic.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static long loops;
static long counter; // protegido por el lock (si el lock funciona)
static int mode;     // 0 flag, 1 peterson, 2 fence

// --- lock con bandera (OSTEP fig. 28.1) ---
static atomic_int busy;

static void flag_lock(void) {
    while (atomic_load_explicit(&busy, memory_order_relaxed) == 1)
        ; // esperar
    // <-- aquí otro hilo puede ver busy == 0 también
    atomic_store_explicit(&busy, 1, memory_order_relaxed);
}

static void flag_unlock(void) {
    atomic_store_explicit(&busy, 0, memory_order_relaxed);
}

// --- Peterson ---
static atomic_int flag[2]; // flag[i] = 1: el hilo i quiere entrar
static atomic_int turn;    // a quién se le cede el paso

static void peterson_lock(int me) {
    int other = 1 - me;
    atomic_store_explicit(&flag[me], 1, memory_order_relaxed);
    atomic_store_explicit(&turn, other, memory_order_relaxed);
    if (mode == 2)
        // Ningún load de abajo puede adelantarse a los stores de arriba.
        atomic_thread_fence(memory_order_seq_cst);
    while (atomic_load_explicit(&flag[other], memory_order_acquire) == 1 &&
           atomic_load_explicit(&turn, memory_order_relaxed) == other)
        ; // esperar
}

static void peterson_unlock(int me) {
    atomic_store_explicit(&flag[me], 0, memory_order_release);
}

static void *worker(void *arg) {
    int me = (int)(long)arg;
    for (long i = 0; i < loops; i++) {
        if (mode == 0)
            flag_lock();
        else
            peterson_lock(me);
        counter = counter + 1; // sección crítica
        if (mode == 0)
            flag_unlock();
        else
            peterson_unlock(me);
    }
    return NULL;
}

int main(int argc, char *argv[]) {
    if (argc < 2) {
        fprintf(stderr, "uso: %s flag|peterson|fence [N]\n", argv[0]);
        return 1;
    }
    if (strcmp(argv[1], "flag") == 0)
        mode = 0;
    else if (strcmp(argv[1], "peterson") == 0)
        mode = 1;
    else if (strcmp(argv[1], "fence") == 0)
        mode = 2;
    else {
        fprintf(stderr, "modo desconocido: %s\n", argv[1]);
        return 1;
    }
    loops = (argc > 2) ? atol(argv[2]) : 1000000;

    pthread_t t0, t1;
    pthread_create(&t0, NULL, worker, (void *)0L);
    pthread_create(&t1, NULL, worker, (void *)1L);
    pthread_join(t0, NULL);
    pthread_join(t1, NULL);

    long expected = 2 * loops;
    printf("%s: perdidas %ld de %ld\n", argv[1], expected - counter,
           expected);
    return 0;
}

// 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;
}

// rvatomics.c — las tres primitivas de hardware, compiladas para RISC-V.
// No se ejecuta: se compila con el compilador cruzado para ver qué
// instrucciones genera cada una (make rv deja el resultado en rvatomics.s).
//
//   test_and_set      -> amoswap.w.aq   (intercambio atómico)
//   compare_and_swap  -> lazo lr.w / sc.w   (load-reserved, store-conditional)
//   fetch_and_add     -> amoadd.w       (suma atómica)

// TestAndSet: escribe 1 y devuelve el valor viejo.
int test_and_set(int *p) {
    return __atomic_exchange_n(p, 1, __ATOMIC_ACQUIRE);
}

// CompareAndSwap: si *p == expected, escribe new. Devuelve el valor viejo.
int compare_and_swap(int *p, int expected, int new) {
    __atomic_compare_exchange_n(p, &expected, new, 0, __ATOMIC_ACQ_REL,
                                __ATOMIC_ACQUIRE);
    return expected; // queda con el valor que había en *p
}

// FetchAndAdd: suma 1 y devuelve el valor viejo (el "ticket").
int fetch_and_add(int *p) {
    return __atomic_fetch_add(p, 1, __ATOMIC_RELAXED);
}

CFLAGS = -Wall -Wextra -g
CFLAGS += -O2 -pthread
PROGS  = bench peterson hash list queue
# Las soluciones aún no publicadas (code/.ocultos) no están en el repositorio:
# se omiten los programas sin fuente y sus líneas en las pruebas.
PROGS := $(foreach p,$(PROGS),$(if $(wildcard $(p).c),$(p)))
RUN    = $(if $(wildcard $(1).c),./$(1),@: sin $(1).c)

all: $(PROGS)

bench: bench.c locks.h
	$(CC) $(CFLAGS) -o $@ bench.c

# peterson sin -O2: así el compilador no reordena nada y lo que se ve es
# solo el reordenamiento del procesador.
peterson: peterson.c
	$(CC) -Wall -Wextra -g -O0 -pthread -o $@ peterson.c

hash list queue: %: %.c
	$(CC) $(CFLAGS) -o $@ $<

# Prueba rápida (pocos segundos) de todos los programas.
test: $(PROGS)
	./peterson flag 1000000
	./peterson peterson 1000000
	./peterson fence 1000000
	$(call RUN,bench) nada 4 100000
	$(call RUN,bench) tabla 100000
	./hash global 4
	./hash bucket 4
	./list uno 4
	./list hoh 4
	./queue 4

# Ver las instrucciones atómicas de RISC-V (necesita riscv64-linux-gnu-gcc).
rv: rvatomics.c
	riscv64-linux-gnu-gcc -O2 -S -o rvatomics.s rvatomics.c
	grep -E 'amo|lr\.|sc\.' rvatomics.s

clean:
	rm -f $(PROGS) rvatomics.s

.PHONY: all test rv clean