/*
 * BAD: Scattered Linked List Traversal
 * =====================================
 * This program creates a linked list with nodes scattered randomly in memory,
 * simulating real-world fragmented allocation patterns.
 * This causes terrible cache behavior due to random memory access.
 *
 * Compile: make list_scattered
 * Run:     ./list_scattered
 * Profile: perf stat -e cache-misses,cache-references ./list_scattered
 */

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <time.h>

#define N 10000000  /* 10 million elements */

struct node {
    int value;
    struct node *next;
};

double get_time(void) {
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return ts.tv_sec + ts.tv_nsec / 1e9;
}

/* Fast deterministic PRNG - much faster than rand() */
static uint64_t xorshift64_state = 42;

static inline uint64_t xorshift64(void) {
    uint64_t x = xorshift64_state;
    x ^= x << 13;
    x ^= x >> 7;
    x ^= x << 17;
    xorshift64_state = x;
    return x;
}

long sum_list(struct node *head) {
    long sum = 0;
    struct node *curr = head;
    while (curr != NULL) {
        sum += curr->value;
        curr = curr->next;
    }
    return sum;
}

/*
 * Create linked list with nodes scattered in memory (worst case for cache)
 * Each node is allocated individually, then shuffled and linked randomly.
 */
struct node *create_list_scattered(int n) {
    struct node **nodes = malloc(n * sizeof(struct node *));
    if (!nodes) {
        perror("malloc");
        exit(1);
    }

    /* Allocate each node separately - they end up scattered in heap */
    for (int i = 0; i < n; i++) {
        nodes[i] = malloc(sizeof(struct node));
        if (!nodes[i]) {
            perror("malloc node");
            exit(1);
        }
        nodes[i]->value = i % 100;
    }

    /* Shuffle the order (Fisher-Yates) to ensure random access pattern */
    for (int i = n - 1; i > 0; i--) {
        int j = xorshift64() % (i + 1);
        struct node *tmp = nodes[i];
        nodes[i] = nodes[j];
        nodes[j] = tmp;
    }

    /* Link them in shuffled order */
    for (int i = 0; i < n - 1; i++) {
        nodes[i]->next = nodes[i + 1];
    }
    nodes[n - 1]->next = NULL;

    struct node *head = nodes[0];
    free(nodes);  /* Free the pointer array, not the nodes */
    return head;
}

void free_scattered_list(struct node *head) {
    while (head != NULL) {
        struct node *next = head->next;
        free(head);
        head = next;
    }
}

int main(void) {
    printf("Scattered Linked List Traversal (%d elements)\n", N);
    printf("Each node allocated individually, then linked in random order.\n");
    printf("This causes maximum cache thrashing.\n\n");

    printf("Creating scattered linked list (this takes a while)...\n");
    struct node *list = create_list_scattered(N);

    /* Warm up */
    sum_list(list);

    double start = get_time();
    long result = sum_list(list);
    double elapsed = get_time() - start;

    printf("Scattered list sum: %ld in %.4f seconds\n\n", result, elapsed);

    printf("To see cache behavior, run:\n");
    printf("  perf stat -e cache-misses,cache-references ./list_scattered\n");

    free_scattered_list(list);
    return 0;
}