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