#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

#define ENTRIES (32768)
#define ITERS   (10000)

typedef struct list list_item;

struct list
{
    list_item     *next;
    char *volatile data;    /* volatile to avoid being optimized away */
};


list_item   a[ENTRIES];

int rrand(int range)
{
    return (int)(range * drand48());
}

void scramble(void)
{
    int i, j;
    int scram[ENTRIES];

    /* Scramble table for linked list */
    for (i = 0; i < ENTRIES; i++)
        scram[i] = i;

    /* Fisher-Yates shuffle */
    for (i = ENTRIES - 1; i >= 0; i--)
    {
        int j  = rrand(i + 1);
        int si = scram[i];
        int sj = scram[j];
        scram[i] = sj;
        scram[j] = si;
    }

    /* Generate randomly scrambled circular list in A */
    for (i = 1, j = 0; i < ENTRIES; i++)
    {
        int si = scram[i];
        a[j].next = &a[si];
        j = si;
    }

    a[j].next = &a[0];
}


void benchmark(int iters)
{
    int i, j;
    list_item *p = &a[0];

    for (i = 0; i < iters; i++)
        for (j = 0; j < ENTRIES; j++)
        {
            p->data++;
            p = p->next;
        }
}

double get_time(void)
{
    struct timeval now;
    double seconds;

    gettimeofday(&now, NULL);
    seconds = (double)now.tv_sec + (double)now.tv_usec * 1e-6;
    return seconds;
}

int main()
{
    double t1, t2;

    srand48(1);

    while (1)
    {
        scramble();
        t1 = get_time();
        benchmark(ITERS);
        t2 = get_time();
        printf("%10.3fms\n", 1000. * (t2 - t1)); fflush(stdout);
    }

    return 0;
}