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