// paging.c — simulador de políticas de reemplazo de páginas.
//
// Recorre una secuencia de referencias a páginas con una memoria de N marcos
// y dice, para cada referencia, si fue acierto o fallo, qué página se expulsó
// y cómo quedaron los marcos. Sirve para verificar a mano los ejemplos de la
// semana 8 (OPT, FIFO, aleatoria, LRU y reloj).
//
// Uso:
//   ./paging [-p política] [-n marcos] [-s semilla] ref ref ...
//   ./paging -p all  -n 3 ref ...      resumen de todas las políticas
//   ./paging -p fifo -c 5 ref ...      fallos con 1, 2, ..., 5 marcos
//   ./paging -p rand -t 10000 ref ...  distribución de fallos de RAND
// Políticas: opt, fifo, rand, lru, clock (por defecto: fifo).
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#define MAX_FRAMES 64
#define MAX_REFS 4096
#define EMPTY (-1)

enum policy { OPT, FIFO, RAND, LRU, CLOCK, NPOLICIES };
static const char *names[NPOLICIES] = {"opt", "fifo", "rand", "lru", "clock"};

struct sim {
    enum policy pol;
    int nframes;
    int frame[MAX_FRAMES];   // página en cada marco, o EMPTY
    long loaded[MAX_FRAMES]; // instante en que entró la página (FIFO)
    long used[MAX_FRAMES];   // instante del último uso (LRU)
    int refbit[MAX_FRAMES];  // bit de referencia (reloj)
    int hand;                // manecilla del reloj
};

static int refs[MAX_REFS];
static int nrefs;

static int find(const struct sim *s, int page) {
    for (int i = 0; i < s->nframes; i++)
        if (s->frame[i] == page)
            return i;
    return -1;
}

// Elige el marco víctima. Solo se llama cuando no hay marcos libres.
static int victim(struct sim *s, int now) {
    int v = 0;
    switch (s->pol) {
    case OPT: {
        // La página cuyo próximo uso está más lejos (o que no se vuelve a
        // usar). Empate entre páginas que no se usan más: la más antigua.
        long best = -1;
        for (int i = 0; i < s->nframes; i++) {
            long next = MAX_REFS + 1;
            for (int t = now + 1; t < nrefs; t++)
                if (refs[t] == s->frame[i]) {
                    next = t;
                    break;
                }
            if (next > best || (next == best && s->loaded[i] < s->loaded[v])) {
                best = next;
                v = i;
            }
        }
        break;
    }
    case FIFO: // la que entró primero
        for (int i = 1; i < s->nframes; i++)
            if (s->loaded[i] < s->loaded[v])
                v = i;
        break;
    case LRU: // la usada hace más tiempo
        for (int i = 1; i < s->nframes; i++)
            if (s->used[i] < s->used[v])
                v = i;
        break;
    case RAND:
        v = rand() % s->nframes;
        break;
    case CLOCK: // avanzar la manecilla, dando segunda oportunidad
        while (s->refbit[s->hand] == 1) {
            s->refbit[s->hand] = 0;
            s->hand = (s->hand + 1) % s->nframes;
        }
        v = s->hand;
        break;
    default:
        break;
    }
    return v;
}

// Espacios que faltan para que s ocupe width columnas (UTF-8: los bytes de
// continuación no ocupan columna).
static int pad(const char *s, int width) {
    int cols = 0;
    for (; *s; s++)
        if ((*s & 0xC0) != 0x80)
            cols++;
    return cols < width ? width - cols : 0;
}

// Escribe en buf el estado de los marcos, en orden de marco.
static void show_frames(const struct sim *s, char *buf, size_t len) {
    size_t off = 0;
    off += snprintf(buf + off, len - off, "[");
    for (int i = 0; i < s->nframes && off < len; i++) {
        const char *sep = (i == 0) ? "" : " ";
        if (s->frame[i] == EMPTY)
            off += snprintf(buf + off, len - off, "%s-", sep);
        else if (s->pol == CLOCK)
            off += snprintf(buf + off, len - off, "%s%d%s%d", sep, s->frame[i],
                            (i == s->hand) ? "<" : ":", s->refbit[i]);
        else
            off += snprintf(buf + off, len - off, "%s%d", sep, s->frame[i]);
    }
    if (off < len)
        snprintf(buf + off, len - off, "]");
}

// Simula la política sobre refs[]. Si verbose, imprime una fila por
// referencia. Retorna el número de fallos.
static int run(enum policy pol, int nframes, int verbose) {
    struct sim s = {.pol = pol, .nframes = nframes, .hand = 0};
    int misses = 0, cold = 0;
    char seen[MAX_REFS] = {0}; // páginas ya vistas (para fallos compulsivos)
    char buf[256];

    for (int i = 0; i < nframes; i++)
        s.frame[i] = EMPTY;
    if (verbose) {
        printf("política %s, %d marcos%s\n", names[pol], nframes,
               pol == CLOCK ? "  (pág:bit, < = manecilla)" : "");
        printf("%4s  %-14s  %7s  %s\n", "ref", "resultado", "expulsa", "marcos");
    }
    for (int t = 0; t < nrefs; t++) {
        int page = refs[t];
        int f = find(&s, page);
        int evicted = EMPTY;
        int compulsory = 0, hit = (f >= 0);
        if (hit) { // acierto
            s.used[f] = t;
            s.refbit[f] = 1;
        } else { // fallo: buscar un marco libre o elegir una víctima
            misses++;
            if (page >= 0 && page < MAX_REFS && !seen[page])
                compulsory = 1, cold++;
            f = find(&s, EMPTY);
            if (f < 0) {
                f = victim(&s, t);
                evicted = s.frame[f];
            } else if (pol == CLOCK) {
                s.hand = f; // los marcos libres se llenan en orden
            }
            s.frame[f] = page;
            s.loaded[f] = t;
            s.used[f] = t;
            s.refbit[f] = 1;
            if (pol == CLOCK)
                s.hand = (f + 1) % nframes;
        }
        if (page >= 0 && page < MAX_REFS)
            seen[page] = 1;
        if (verbose) {
            show_frames(&s, buf, sizeof(buf));
            char ev[16] = "-";
            if (evicted != EMPTY)
                snprintf(ev, sizeof(ev), "%d", evicted);
            const char *what =
                hit ? "acierto" : (compulsory ? "fallo (frío)" : "fallo");
            printf("%4d  %s%*s  %7s  %s\n", page, what, pad(what, 14), "",
                   ev, buf);
        }
    }
    if (verbose)
        printf("aciertos %d, fallos %d (%d fríos), tasa de aciertos %.1f%%\n",
               nrefs - misses, misses, cold,
               100.0 * (nrefs - misses) / nrefs);
    return misses;
}

static void usage(const char *prog) {
    fprintf(stderr,
            "uso: %s [-p opt|fifo|rand|lru|clock|all] [-n marcos] "
            "[-s semilla] [-c max_marcos] [-t intentos] ref ...\n",
            prog);
    exit(1);
}

int main(int argc, char *argv[]) {
    int nframes = 3, curve = 0, trials = 0, all = 0;
    unsigned seed = 1;
    enum policy pol = FIFO;
    int opt;

    while ((opt = getopt(argc, argv, "p:n:s:c:t:")) != -1) {
        switch (opt) {
        case 'p':
            if (strcmp(optarg, "all") == 0) {
                all = 1;
                break;
            }
            pol = NPOLICIES;
            for (int i = 0; i < NPOLICIES; i++)
                if (strcmp(optarg, names[i]) == 0)
                    pol = i;
            if (pol == NPOLICIES)
                usage(argv[0]);
            break;
        case 'n': nframes = atoi(optarg); break;
        case 's': seed = (unsigned)atoi(optarg); break;
        case 'c': curve = atoi(optarg); break;
        case 't': trials = atoi(optarg); break;
        default: usage(argv[0]);
        }
    }
    if (nframes < 1 || nframes > MAX_FRAMES || curve > MAX_FRAMES ||
        optind >= argc)
        usage(argv[0]);
    for (int i = optind; i < argc && nrefs < MAX_REFS; i++)
        refs[nrefs++] = atoi(argv[i]);

    printf("referencias:");
    for (int i = 0; i < nrefs; i++)
        printf(" %d", refs[i]);
    printf("\n");

    if (all) { // una línea por política
        printf("%d marcos\n%-6s %8s %6s %8s\n", nframes, "", "aciertos",
               "fallos", "tasa");
        for (int p = 0; p < NPOLICIES; p++) {
            srand(seed);
            int m = run(p, nframes, 0);
            printf("%-6s %8d %6d %7.1f%%\n", names[p], nrefs - m, m,
                   100.0 * (nrefs - m) / nrefs);
        }
    } else if (curve > 0) { // fallos según el número de marcos
        printf("política %s\n%6s %6s\n", names[pol], "marcos", "fallos");
        for (int n = 1; n <= curve; n++) {
            srand(seed);
            printf("%6d %6d\n", n, run(pol, n, 0));
        }
    } else if (trials > 0) { // distribución de fallos con RAND
        int hist[MAX_REFS + 1] = {0};
        double sum = 0;
        for (int t = 0; t < trials; t++) {
            srand(seed + t);
            int m = run(RAND, nframes, 0);
            hist[m]++;
            sum += m;
        }
        printf("rand, %d marcos, %d intentos: fallos promedio %.2f\n",
               nframes, trials, sum / trials);
        printf("%6s %8s\n", "fallos", "veces");
        for (int m = 0; m <= nrefs; m++)
            if (hist[m] > 0)
                printf("%6d %8d\n", m, hist[m]);
    } else {
        srand(seed);
        run(pol, nframes, 1);
    }
    return 0;
}