/* hp_traverse.c - cost of hp_protect on a read-only traversal.
 *
 * A singly linked list of L nodes is walked hand-over-hand with two hazard
 * pointers, as in Michael's list-based set: protect curr from prev->next,
 * then swap roles. The list is never modified, so validation always succeeds
 * and the measured difference between builds is the cost of publishing.
 *
 * usage: hp_traverse [-t threads] [-l length] [-n walks_per_thread] [-r]
 *   -r  link the nodes in a random permutation of their allocation order
 * Build with -DHP_K=2 and one of: (default, seq_cst publish), -DHP_ASYM=1,
 * -DHP_NONE=1 (plain acquire loads).
 */
#define _GNU_SOURCE
#include <getopt.h>
#include <pthread.h>
#include <time.h>
#include "hp.h"

typedef struct lnode {
    _Atomic(void *) next;
    long key;
} lnode_t;

static _Atomic(void *) head;
static int nthreads = 1, len = 1000;
static long walks = 20000;
static pthread_barrier_t bar;
static atomic_long sink;

static void *reader(void *arg)
{
    (void)arg;
    hp_local_t l;
    int id = hp_register(&l);
    long sum = 0;
    pthread_barrier_wait(&bar);
    for (long w = 0; w < walks; w++) {
        _Atomic(void *) *src = &head;
        int k = 0;
        lnode_t *cur;
        while ((cur = hp_protect(id, k, src)) != NULL) {
            sum += cur->key;
            src = &cur->next;
            k ^= 1;             /* cur stays covered while its successor is protected */
        }
        hp_clear(id, 0);
        hp_clear(id, 1);
    }
    atomic_fetch_add(&sink, sum);
    free(l.rlist);
    return NULL;
}

int main(int argc, char **argv)
{
    int c, shuffle = 0;
    while ((c = getopt(argc, argv, "t:l:n:r")) != -1) {
        switch (c) {
        case 'r': shuffle = 1; break;
        case 't': nthreads = atoi(optarg); break;
        case 'l': len = atoi(optarg); break;
        case 'n': walks = atol(optarg); break;
        default: return 2;
        }
    }
    if (nthreads < 1 || nthreads > HP_MAX_THREADS || len < 1) return 2;
    hp_global_init(1, 0);
    lnode_t **v = malloc(sizeof *v * (size_t)len);
    for (int i = 0; i < len; i++) { v[i] = malloc(sizeof **v); v[i]->key = i + 1; }
    if (shuffle) {          /* link in random address order: every hop is a cache miss */
        srand(1);
        for (int i = len - 1; i > 0; i--) {
            int j = rand() % (i + 1);
            lnode_t *tmp = v[i]; v[i] = v[j]; v[j] = tmp;
        }
    }
    for (int i = len - 1; i >= 0; i--) {
        atomic_store(&v[i]->next, atomic_load(&head));
        atomic_store(&head, v[i]);
    }
    free(v);
    pthread_t th[HP_MAX_THREADS];
    pthread_barrier_init(&bar, NULL, (unsigned)nthreads + 1);
    for (int t = 0; t < nthreads; t++) pthread_create(&th[t], NULL, reader, NULL);
    struct timespec t0, t1;
    pthread_barrier_wait(&bar);
    clock_gettime(CLOCK_MONOTONIC, &t0);
    for (int t = 0; t < nthreads; t++) pthread_join(th[t], NULL);
    clock_gettime(CLOCK_MONOTONIC, &t1);
    double ns = (double)(t1.tv_sec - t0.tv_sec) * 1e9 + (double)(t1.tv_nsec - t0.tv_nsec);
    long expect = (long)nthreads * walks * ((long)len * (len + 1) / 2);
    printf("none=%d asym=%d threads=%d len=%d shuffle=%d walks=%ld ns_per_node=%.3f check=%s\n",
           HP_NONE, HP_ASYM, nthreads, len, shuffle, walks, ns / ((double)walks * len),
           atomic_load(&sink) == expect ? "OK" : "FAIL");
    for (lnode_t *n = atomic_load(&head), *nx; n; n = nx) { nx = atomic_load(&n->next); free(n); }
    return atomic_load(&sink) == expect ? 0 : 1;
}