// banker.c — algoritmo del banquero y detección de deadlock con varias
// instancias por recurso.
//
// Uso: ./banker ARCHIVO      lee un estado y lo analiza
//      ./banker -            lee el estado de la entrada estándar
//
// El archivo tiene secciones; '#' empieza un comentario hasta fin de línea:
//
//   recursos   A B C          nombres de los tipos de recurso
//   disponible 2 1 2          instancias libres de cada tipo
//   maximo                    demanda máxima declarada (para evitar), o
//   solicitud                 lo que cada proceso pide ahora (para detectar)
//   P1 5 2 2                  una fila por proceso: nombre y un número por tipo
//   ...
//   asignado                  lo que cada proceso tiene ahora
//   P1 1 1 0
//   ...
//   pide P1 1 0 1             (solo con maximo) solicitudes, en orden
//
// Con maximo: Necesidad = Máximo - Asignado. Dice si el estado es seguro,
// con una secuencia segura, y evalúa cada `pide`: la concede solo si el
// estado que resulta es seguro (y entonces la aplica antes de la siguiente).
// Con solicitud: el mismo algoritmo con Solicitud en vez de Necesidad. Los
// procesos que no pueden terminar están en deadlock; luego prueba abortar a
// cada uno por separado.
//
// En cada vuelta se elige el PRIMER proceso (en el orden del archivo) que
// puede terminar; puede haber otras secuencias seguras.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXP 16
#define MAXR 8
#define MAXREQ 16
#define NAMELEN 16

static int nres, nproc;
static char res[MAXR][NAMELEN];
static char proc[MAXP][NAMELEN];
static int avail[MAXR];
static int max[MAXP][MAXR];     // Máximo (evitar) o Solicitud (detectar)
static int alloc[MAXP][MAXR];
static int detect;              // 1 si el archivo trae `solicitud`

static int nreq;
static int req_p[MAXREQ];
static int req_v[MAXREQ][MAXR];

static FILE *in;
static int line = 1;

static void fail(const char *msg, const char *tok) {
    fprintf(stderr, "línea %d: %s%s%s\n", line, msg, tok ? ": " : "", tok ? tok : "");
    exit(1);
}

// Siguiente palabra del archivo, o NULL al final. Salta comentarios.
static char *word(void) {
    static char buf[64];
    int c, n = 0;
    for (;;) {
        c = getc(in);
        if (c == '#')
            while (c != '\n' && c != EOF)
                c = getc(in);
        if (c == '\n')
            line++;
        if (c == EOF)
            return NULL;
        if (c != ' ' && c != '\t' && c != '\n' && c != '\r')
            break;
    }
    while (c != EOF && c != ' ' && c != '\t' && c != '\n' && c != '\r' && c != '#') {
        if (n < (int)sizeof buf - 1)
            buf[n++] = c;
        c = getc(in);
    }
    if (c != EOF)
        ungetc(c, in);
    buf[n] = '\0';
    return buf;
}

static int number(void) {
    char *w = word(), *end;
    if (w == NULL)
        fail("falta un número", NULL);
    long v = strtol(w, &end, 10);
    if (*end != '\0' || v < 0)
        fail("se esperaba un entero >= 0", w);
    return (int)v;
}

static void numbers(int *v) {
    for (int j = 0; j < nres; j++)
        v[j] = number();
}

static int find_proc(const char *name, int add) {
    for (int i = 0; i < nproc; i++)
        if (strcmp(proc[i], name) == 0)
            return i;
    if (!add)
        fail("proceso desconocido", name);
    if (nproc == MAXP)
        fail("demasiados procesos", name);
    snprintf(proc[nproc], NAMELEN, "%s", name);
    return nproc++;
}

static int keyword(const char *w) {
    return !strcmp(w, "recursos") || !strcmp(w, "disponible") ||
           !strcmp(w, "maximo") || !strcmp(w, "solicitud") ||
           !strcmp(w, "asignado") || !strcmp(w, "pide");
}

static void parse(void) {
    char *w = word();
    int (*rows)[MAXR] = NULL;   // sección de filas en curso
    while (w != NULL) {
        if (!strcmp(w, "recursos")) {
            while ((w = word()) != NULL && !keyword(w)) {
                if (nres == MAXR)
                    fail("demasiados recursos", w);
                snprintf(res[nres++], NAMELEN, "%s", w);
            }
            continue;
        }
        if (nres == 0)
            fail("la primera sección debe ser `recursos`", w);
        if (!strcmp(w, "disponible")) {
            numbers(avail);
            rows = NULL;
        } else if (!strcmp(w, "maximo") || !strcmp(w, "solicitud")) {
            detect = !strcmp(w, "solicitud");
            rows = max;
        } else if (!strcmp(w, "asignado")) {
            rows = alloc;
        } else if (!strcmp(w, "pide")) {
            if (nreq == MAXREQ)
                fail("demasiados pedidos", NULL);
            char *p = word();
            if (p == NULL)
                fail("falta el proceso del pedido", NULL);
            req_p[nreq] = find_proc(p, 0);
            numbers(req_v[nreq++]);
            rows = NULL;
        } else if (rows != NULL) {
            numbers(rows[find_proc(w, 1)]);
        } else {
            fail("palabra inesperada", w);
        }
        w = word();
    }
    if (nproc == 0)
        fail("no hay procesos", NULL);
}

static void vprint(const int *v) {
    for (int j = 0; j < nres; j++)
        printf("%s%d", j ? " " : "", v[j]);
}

static int leq(const int *a, const int *b) {
    for (int j = 0; j < nres; j++)
        if (a[j] > b[j])
            return 0;
    return 1;
}

// Necesidad (evitar) o Solicitud (detectar) del proceso i.
static void need(int i, int *v) {
    for (int j = 0; j < nres; j++)
        v[j] = detect ? max[i][j] : max[i][j] - alloc[i][j];
}

// El algoritmo de seguridad. Devuelve cuántos procesos terminan; deja en
// seq el orden y en finish quién terminó. Con verbose, muestra cada paso.
// `skip` (o -1) es un proceso que se considera ya abortado.
static int safety(int *seq, int *finish, int verbose, int skip) {
    int work[MAXR], n = 0, v[MAXR];
    memcpy(work, avail, sizeof work);
    for (int i = 0; i < nproc; i++)
        finish[i] = 0;
    if (skip >= 0) {
        finish[skip] = 1;
        for (int j = 0; j < nres; j++)
            work[j] += alloc[skip][j];
    }
    for (;;) {
        int found = -1;
        for (int i = 0; i < nproc && found < 0; i++) {
            need(i, v);
            if (!finish[i] && leq(v, work))
                found = i;
        }
        if (verbose) {
            printf("  trabajo ");
            vprint(work);
        }
        if (found < 0)
            break;
        if (verbose) {
            printf(": %s %s ", proc[found], detect ? "pide" : "necesita");
            need(found, v);
            vprint(v);
            printf(", cabe; termina y devuelve ");
            vprint(alloc[found]);
            printf("\n");
        }
        for (int j = 0; j < nres; j++)
            work[j] += alloc[found][j];
        finish[found] = 1;
        seq[n++] = found;
    }
    if (verbose) {
        int rest = 0;
        for (int i = 0; i < nproc; i++)
            rest += !finish[i] && i != skip;
        if (rest == 0) {
            printf(": todos terminaron");
        } else {
            printf(": %s cabe (", n > 0 ? "nadie más" : "nadie");
            for (int i = 0, k = 0; i < nproc; i++) {
                if (finish[i])
                    continue;
                need(i, v);
                printf("%s%s ", k++ ? ", " : "", proc[i]);
                vprint(v);
            }
            printf(")");
        }
        printf("\n");
    }
    return n;
}

// Imprime s y completa con espacios hasta w columnas (cuenta caracteres UTF-8).
static void cell(const char *s, int w) {
    int n = 0;
    for (const char *p = s; *p; p++)
        n += ((unsigned char)*p & 0xC0) != 0x80;
    printf("%s%*s", s, w > n ? w - n : 0, "");
}

static void vcell(const int *v, int w) {
    char buf[64];
    int n = 0;
    for (int j = 0; j < nres; j++)
        n += snprintf(buf + n, sizeof buf - n, "%s%d", j ? " " : "", v[j]);
    cell(buf, w);
}

static void print_state(void) {
    int total[MAXR], v[MAXR], w = 2 * nres + 3;
    if (w < 11)
        w = 11;
    for (int j = 0; j < nres; j++) {
        total[j] = avail[j];
        for (int i = 0; i < nproc; i++)
            total[j] += alloc[i][j];
    }
    printf("recursos:");
    for (int j = 0; j < nres; j++)
        printf(" %s", res[j]);
    printf("   total: ");
    vprint(total);
    printf("   disponible: ");
    vprint(avail);
    printf("\n");
    cell("proceso", 9);
    cell(detect ? "solicitud" : "máximo", w);
    if (detect)
        printf("asignado\n");
    else
        cell("asignado", w);
    printf("%s", detect ? "" : "necesidad\n");
    for (int i = 0; i < nproc; i++) {
        cell(proc[i], 9);
        vcell(max[i], w);
        if (detect)
            vprint(alloc[i]);
        else
            vcell(alloc[i], w);
        if (!detect) {
            need(i, v);
            vprint(v);
            if (!leq(alloc[i], max[i]) || !leq(max[i], total))
                printf("   (inválido: asignado > máximo o máximo > total)");
        }
        printf("\n");
    }
}

static void print_seq(const int *seq, int n) {
    for (int k = 0; k < n; k++)
        printf("%s%s", k ? " " : "", proc[seq[k]]);
}

static void avoid(void) {
    int seq[MAXP], finish[MAXP], v[MAXR];
    printf("\n¿es seguro?\n");
    int n = safety(seq, finish, 1, -1);
    if (n == nproc) {
        printf("estado seguro: ");
        print_seq(seq, n);
        printf("\n");
    } else {
        printf("estado inseguro\n");
    }

    for (int r = 0; r < nreq; r++) {
        int i = req_p[r], *q = req_v[r];
        printf("\npide %s ", proc[i]);
        vprint(q);
        printf("\n");
        need(i, v);
        if (!leq(q, v)) {
            printf("  pide más que su necesidad (");
            vprint(v);
            printf("): error, se rechaza\n");
            continue;
        }
        if (!leq(q, avail)) {
            printf("  no hay suficiente disponible (");
            vprint(avail);
            printf("): %s espera\n", proc[i]);
            continue;
        }
        // Simular que se concede.
        for (int j = 0; j < nres; j++) {
            avail[j] -= q[j];
            alloc[i][j] += q[j];
        }
        printf("  cabe en necesidad y disponible; si se concede, disponible = ");
        vprint(avail);
        printf("\n");
        n = safety(seq, finish, 1, -1);
        if (n == nproc) {
            printf("  seguro (");
            print_seq(seq, n);
            printf("): se concede\n");
        } else {
            printf("  inseguro: se niega; %s espera y el estado vuelve atrás\n", proc[i]);
            for (int j = 0; j < nres; j++) {
                avail[j] += q[j];
                alloc[i][j] -= q[j];
            }
        }
    }
}

static void detection(void) {
    int seq[MAXP], finish[MAXP], dead[MAXP], nd = 0;
    printf("\ndetección (solicitud en lugar de necesidad)\n");
    int n = safety(seq, finish, 1, -1);
    if (n == nproc) {
        printf("sin deadlock: ");
        print_seq(seq, n);
        printf(" pueden terminar en ese orden\n");
        return;
    }
    printf("deadlock:");
    for (int i = 0; i < nproc; i++)
        if (!finish[i]) {
            dead[nd++] = i;
            printf(" %s", proc[i]);
        }
    printf("\n\nrecuperación: abortar a uno solo\n");
    for (int k = 0; k < nd; k++) {
        int f2[MAXP], s2[MAXP];
        int m = safety(s2, f2, 0, dead[k]);
        printf("  abortar %s (libera ", proc[dead[k]]);
        vprint(alloc[dead[k]]);
        if (m == nproc - 1) {
            printf("): los demás terminan: ");
            print_seq(s2, m);
            printf("\n");
        } else {
            printf("): no basta, siguen bloqueados:");
            for (int i = 0; i < nproc; i++)
                if (!f2[i])
                    printf(" %s", proc[i]);
            printf("\n");
        }
    }
}

int main(int argc, char *argv[]) {
    if (argc != 2) {
        fprintf(stderr, "uso: %s ARCHIVO   (o - para la entrada estándar)\n", argv[0]);
        return 1;
    }
    in = strcmp(argv[1], "-") == 0 ? stdin : fopen(argv[1], "r");
    if (in == NULL) {
        perror(argv[1]);
        return 1;
    }
    parse();
    print_state();
    if (detect) {
        if (nreq > 0)
            fail("`pide` solo tiene sentido con `maximo`", NULL);
        detection();
    } else {
        avoid();
    }
    return 0;
}