11 - Ejemplo 1: Resolución de dominios (dominio -> IP)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
  const char *dominio;
  const char *ip;
} RegistroDNS;

typedef enum { CELDA_VACIA, CELDA_OCUPADA, CELDA_BORRADA } Estado;

typedef struct {
  RegistroDNS valor;
  Estado estado;
} Entrada;

typedef struct {
  Entrada *celdas;
  unsigned long capacidad;
  unsigned long cantidad;
} TablaDNS;

static unsigned long hash1(const char *clave, unsigned long cap) {
  unsigned long h = 5381;
  int c;
  while ((c = *clave++) != 0) h = ((h << 5) + h) + (unsigned long)c; /* djb2 */
  return h % cap;
}

static unsigned long hash2(const char *clave, unsigned long cap) {
  unsigned long h = 0;
  int c;
  while ((c = *clave++) != 0) h = h * 131 + (unsigned long)c;
  return 1 + (h % (cap - 1));
}

static int insertar(TablaDNS *t, const char *dominio, const char *ip) {
  unsigned long base = hash1(dominio, t->capacidad);
  unsigned long paso = hash2(dominio, t->capacidad);
  long primera_borrada = -1;
  for (unsigned long i = 0; i < t->capacidad; i++) {
    unsigned long idx = (base + i * paso) % t->capacidad;
    if (t->celdas[idx].estado == CELDA_OCUPADA && strcmp(t->celdas[idx].valor.dominio, dominio) == 0) {
      t->celdas[idx].valor.ip = ip; /* actualiza IP si el dominio ya existia */
      return 1;
    }
    if (t->celdas[idx].estado == CELDA_BORRADA && primera_borrada == -1) primera_borrada = (long)idx;
    if (t->celdas[idx].estado == CELDA_VACIA) {
      unsigned long destino = (primera_borrada != -1) ? (unsigned long)primera_borrada : idx;
      t->celdas[destino].valor.dominio = dominio;
      t->celdas[destino].valor.ip = ip;
      t->celdas[destino].estado = CELDA_OCUPADA;
      t->cantidad++;
      return 1;
    }
  }
  return 0;
}

static RegistroDNS *buscar(TablaDNS *t, const char *dominio) {
  unsigned long base = hash1(dominio, t->capacidad);
  unsigned long paso = hash2(dominio, t->capacidad);
  for (unsigned long i = 0; i < t->capacidad; i++) {
    unsigned long idx = (base + i * paso) % t->capacidad;
    if (t->celdas[idx].estado == CELDA_VACIA) return NULL;
    if (t->celdas[idx].estado == CELDA_OCUPADA && strcmp(t->celdas[idx].valor.dominio, dominio) == 0) {
      return &t->celdas[idx].valor;
    }
  }
  return NULL;
}

static int eliminar(TablaDNS *t, const char *dominio) {
  unsigned long base = hash1(dominio, t->capacidad);
  unsigned long paso = hash2(dominio, t->capacidad);
  for (unsigned long i = 0; i < t->capacidad; i++) {
    unsigned long idx = (base + i * paso) % t->capacidad;
    if (t->celdas[idx].estado == CELDA_VACIA) return 0;
    if (t->celdas[idx].estado == CELDA_OCUPADA && strcmp(t->celdas[idx].valor.dominio, dominio) == 0) {
      t->celdas[idx].estado = CELDA_BORRADA;
      t->cantidad--;
      return 1;
    }
  }
  return 0;
}

static int rehash(TablaDNS *t, unsigned long nueva_capacidad) {
  Entrada *nuevas = malloc(sizeof(Entrada) * nueva_capacidad);
  if (!nuevas) return 0;
  for (unsigned long i = 0; i < nueva_capacidad; i++) {
    nuevas[i].estado = CELDA_VACIA;
    nuevas[i].valor.dominio = NULL;
    nuevas[i].valor.ip = NULL;
  }
  Entrada *viejas = t->celdas;
  unsigned long vieja_cap = t->capacidad;
  t->celdas = nuevas;
  t->capacidad = nueva_capacidad;
  t->cantidad = 0;
  for (unsigned long i = 0; i < vieja_cap; i++) {
    if (viejas[i].estado == CELDA_OCUPADA) {
      insertar(t, viejas[i].valor.dominio, viejas[i].valor.ip);
    }
  }
  free(viejas);
  return 1;
}

int main(void) {
  TablaDNS tabla = {0};
  tabla.capacidad = 11; /* número primo */
  tabla.celdas = malloc(sizeof(Entrada) * tabla.capacidad);
  for (unsigned long i = 0; i < tabla.capacidad; i++) tabla.celdas[i].estado = CELDA_VACIA;

  const char *dominios[] = {
    "google.com",
    "facebook.com",
    "wikipedia.org",
    "youtube.com",
    "github.com"
  };
  const char *ips[] = {
    "142.250.72.206",
    "157.240.22.35",
    "208.80.154.224",
    "142.250.72.238",
    "140.82.114.4"
  };
  unsigned long n = sizeof(dominios) / sizeof(dominios[0]);
  double umbral = 0.7;

  for (unsigned long i = 0; i < n; i++) {
    double alpha = (double)(tabla.cantidad + 1) / (double)tabla.capacidad;
    if (alpha >= umbral) {
      unsigned long nueva = tabla.capacidad * 2 + 1;
      printf("Rehash a %lu (alpha previsto %.2f)\n", nueva, alpha);
      rehash(&tabla, nueva);
    }
    insertar(&tabla, dominios[i], ips[i]);
  }

  RegistroDNS *registro = buscar(&tabla, "github.com");
  printf("github.com -> %s\n", registro ? registro->ip : "no encontrado");

  insertar(&tabla, "google.com", "142.250.72.207"); /* actualización IP */
  registro = buscar(&tabla, "google.com");
  printf("google.com -> %s\n", registro ? registro->ip : "no encontrado");

  eliminar(&tabla, "facebook.com");
  registro = buscar(&tabla, "facebook.com");
  printf("facebook.com -> %s\n", registro ? registro->ip : "no encontrado");

  free(tabla.celdas);
  return 0;
}