// Example program to illustrate hash tables.

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

int
hash(char *s)
{
  return 0;
  int h = s[0] & 0xf;
  if (s[0] == '\0') return h;
  h = h << 4 | (s[1] & 0xf);
  if (s[1] == '\0') return h;
  return h << 4 | (s[2] & 0xf);
}

enum { name_size = 8, name_offset = 7, record_size = 20 };
typedef struct {
  char name[name_size + 1];
  int count;
  int occupied;
} entry;

entry table[16];

#define LEN(x) (sizeof(x)/sizeof((x)[0]))

int probes = 0;

entry *
upsert(char *name)
{
  if (strlen(name) > name_size) abort();
  int h = hash(name) % LEN(table);
  for (int i = 0; i != LEN(table); i++) {
    if (!table[h].occupied) {
      table[h].occupied = 1;
      strcpy(table[h].name, name);
      return &table[h];
    }

    if (0 == strncmp(name, table[h].name, name_size)) return &table[h];

    probes++;
    h++;
    if (h == LEN(table)) h = 0;
  }
  return 0;
}

int
main(int argc, char **argv)
{
  if (argc != 2) {
    fprintf(stderr, "Usage: %s infile.dat\n", argv[0]);
    return -1;
  }

  FILE *fp = fopen(argv[1], "rb");
  if (!fp) {
    perror(argv[1]);
    return 1;
  }

  for (;;) {
    char record[record_size];
    int n = fread(record, sizeof(record), 1, fp);
    if (n == 0) break;
    if (1 != n) {
      perror("fread");
      return 2;
    }

    record[name_offset + name_size] = '\0';
    entry *e = upsert(record + name_offset);
    if (!e) {
      fprintf(stderr, "out of memory\n");
      return 3;
    }

    e->count++;
  }
  fclose(fp);

  for (int i = 0; i != LEN(table); i++) {
    if (!table[i].occupied) continue;
    printf("%8d %s\n", table[i].count, table[i].name);
  }
           
  printf("%d probes\n", probes);

  return 0;
}