// Cross-Reference-Liste, mit Hashtable
//
// Aufruf: xref-hash file ...
//
// Klaus Kusche, 2002, 2026

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

// Größe der Hashtable
// Kleine Primzahl
//#define HASH_PRIME 10007
// Große Primzahl
#define HASH_PRIME 1000003
// Schlecht: Große Zweierpotenz
//#define HASH_PRIME 1048576
// Ganz schlecht: Kleine Zweierpotenz
//#define HASH_PRIME 8192

// Max. Länge einer Input-Zeile
#define LINE_LEN 16384

// Welche Zeichen sind als Anfang eines Wortes erlaubt?
#define is_word_beg(c) (isalpha(c) || ((c) == '_'))

// Welche Zeichen sind innerhalb eines Wortes erlaubt?
#define is_in_word(c) (isalnum(c) || ((c) == '_'))

// Max. Listenlänge in der Statistik-Ausgabe
#define MAX_STAT_LEN  50

// Typ eines Eintrags der Positionsliste
typedef struct _pos_entry {
  const char *filename;      // File, in dem die Position liegt (= argv[...])
  int line;                  // Zeilennummer
  int column;                // Spaltennummer
  struct _pos_entry *next;   // Verkettung zur nächsten Position
} pos_entry;

// Typ eines Eintrags der Wortliste
typedef struct _word_entry {
  const char *text;          // Text des Wortes
  pos_entry *first_pos;      // Head der Positionsliste des Wortes
  pos_entry *last_pos;       // Tail der Positionsliste des Wortes
  struct _word_entry *next;  // Verkettung der Wortliste eines Hashwerts
} word_entry;


// Die Hashfunktion: Berechnet aus einem Wort den Index in die Hashtable,
// also 0 ... (HASH_PRIME - 1)
unsigned int hash(const char *text);
// Liefert einen Pointer auf n mit malloc angeforderte Bytes, mit Fehlerprüfung
void *my_malloc(size_t n);
// Liefert einen Pointer auf eine strdup-Kopie von s, mit Fehlerprüfung
char *save_str(const char *s);
// Liefert einen Pointer auf einen neu angelegten Positionsknoten
pos_entry *new_pos(const char *filename, int line_nr, int col_nr);
// Liefert einen Pointer auf einen neu angelegten Wortknoten
word_entry *new_word(const char *word, pos_entry *pos, word_entry *next);
// Hängt die Position pos *hinten* an die Positionsliste von word an
void add_pos(pos_entry *pos, word_entry *word);
// Speichert eine neue Position des (neuen oder bekannten) Wortes word
void save_word(const char *filename, int line_nr, int col_nr, const char *word);
// Ermittelt und speichert alle Worte in der Zeile line
void read_line(const char *filename, int line_nr, char *line);
// Liest und verarbeitet den angegebenen File zeilenweise
void read_file(const char *filename);
// Gibt alle Positionen der Positionsliste des Wortes word aus
void list_pos(const word_entry *word);
// Sucht das angegebene Wort word im Hashspeicher, gibt seine Positionen aus
void process_word(const char *word);
// Liest und verarbeitet den Input vom Terminal (ein Wort pro Zeile!)
void process_input(void);
// Gibt Statistiken über die Hash-Verteilung aus
void statistics(void);


// Die Hashtable: Enthält die Head-Pointer der Wortlisten
word_entry *hashtable[HASH_PRIME];

// Der Programmname (für Fehlermeldungen)
const char *prog_name;

// Die Hashfunktion: Berechnet aus einem Wort den Index in die Hashtable,
// also 0 ... (HASH_PRIME - 1)
// Verwendet eine 7-Bit-Rotation und Xor pro Zeichen
// und liefert diese Zahl mod Arraygröße
unsigned int hash(const char *text)
{
  unsigned int h = 0;  // muss wegen >> unsigned sein!

  for (const char *p = text; *p != '\0'; ++p) {
    // Einfach, aber gut:
    // Alten Wert 7 Bits nach links rotieren (weil Bit 8 bei ASCII immer 0 ist),
    // Bits des aktuellen Buchstabens mit Xor dazu
    h = ((h << 7) ^ (h >> 25)) ^ *p;
    // Etwas schlechter: 8 Bit Rotate
    //h = (h << 8) ^ (h >> 24) ^ *p;
    // Schlecht: 7 Bit Shift (nur die letzten 4,5 Zeichen beeinflussen h!)
    //h = (h << 7) ^ *p;
    // Ganz schlecht: 8 Bit Shift (nur die letzten 4 Zeichen beeinflussen h!)
    //h = (h << 8) ^ *p;
  }
  
  // das Ergebnis in den gewünschten Wertebereich bringen
  return h % HASH_PRIME;
}

// Liefert einen Pointer auf n mit malloc angeforderte Bytes, 
// mit Fehlerprüfung, bei Fehler: Fehlermeldung und Programm-Abbruch
void *my_malloc(size_t n)
{
  void *p = malloc(n);

  if (p == NULL) {
    fprintf(stderr, "%s: Out of memory\n", prog_name);
    exit(EXIT_FAILURE);
  }

  return p;
}

// Liefert einen Pointer auf eine mit strdup angelegte Kopie von s,
// mit Fehlerprüfung, bei Fehler: Fehlermeldung und Programm-Abbruch
char *save_str(const char *s)
{
  char *p = strdup(s);

  if (p == NULL) {
    fprintf(stderr, "%s: Out of memory\n", prog_name);
    exit(EXIT_FAILURE);
  }

  return p;
}

// Liefert einen Pointer auf einen neu angelegten Positionsknoten
// Die Argumente enthalten die im Knoten einzutragende Position
// Die Verkettung des neuen Knotens wird auf NULL gesetzt
// (weil der Knoten ja hinten an der Positionsliste angehängt wird)
pos_entry *new_pos(const char *filename, int line_nr, int col_nr)
{
  pos_entry *p = (pos_entry *) (my_malloc(sizeof (pos_entry)));

  p->filename = filename;
  p->line = line_nr;
  p->column = col_nr;
  p->next = NULL;

  return p;
}

// Liefert einen Pointer auf einen neu angelegten Wortknoten
// word ist das im Knoten einzutragende Wort, pos dessen erste Position,
// und next ist als Verkettung auf den nächsten Wortknoten einzutragen
//
// Achtung: word darf nicht direkt gespeichert werden
// (weil es auf den internen Zeilenpuffer von read_file zeigt
// und daher beim Lesen der nächsten Zeile überschrieben wird),
// sondern es muss eine dynamisch erzeugte *Kopie* im Knoten gespeichert werden!
word_entry *new_word(const char *word, pos_entry *pos, word_entry *next)
{
  word_entry *w = (word_entry *) (my_malloc(sizeof (word_entry)));

  w->text = save_str(word);
  w->first_pos = w->last_pos = pos;
  w->next = next;

  return w;
}

// Hängt die Position pos *hinten* an die (nichtleere!) Positionsliste
// des Wortknotens wort an
void add_pos(pos_entry *pos, word_entry *word)
{
  word->last_pos->next = pos;
  word->last_pos = pos;
}

// Es wird mit new_pos ein neuer Positionseintrag
//   (filename/line_nr/col_nr) angelegt
//
// Dann wird das Wort word im Hash-Speicher gesucht
// Gibt es das Wort noch nicht, wird mittels new_word
// ein neuer Worteintrag erzeugt (mit dem neuen Pos-Eintrag)
// und *vorne* an die richtige Hashliste angehängt
//
// Gibt es das Wort schon,
// wird der neue Pos-Eintrag mittels add_pos an dessen Positionsliste angehängt
void save_word(const char *filename, int line_nr, int col_nr, const char *word)
{
  // Wir brauchen in jedem Fall einen neuen Pos-Eintrag
  pos_entry *pos = new_pos(filename, line_nr, col_nr);

  // ermittle die für word zuständige Liste im Hash-Array
  unsigned int h = hash(word);
  // durchsuche diese Liste nach word
  for (word_entry *w = hashtable[h]; w != NULL; w = w->next) {
    if (strcmp(w->text, word) == 0) {
      // gefunden! ==> Position pos an das bestehende Wort w anhängen
      add_pos(pos, w);
      return;
    }
  }

  // nicht gefunden: Einen neuen Worteintrag für word mit Position pos erzeugen
  // und vorne in die Liste hashtable[h] einfügen
  hashtable[h] = new_word(word, pos, hashtable[h]);
}

// Ermittelt und speichert alle Worte in der Zeile line
// Achtung: line wird dabei modifiziert!
// filename und line_nr sind die Position der Zeile
void read_line(const char *filename, int line_nr, char *line)
{
  char *line_end = strchr(line, '\0');   // Zeiger auf das \0 am Zeilenende

  // Schleife mit einem Durchlauf pro Wort
  char *word_beg;  // Zeiger auf den ersten Char des nächsten Wortes
  char *word_end;  // Zeiger auf den ersten Char hinter dem Wort
  // Erster Durchlauf beginnt am Zeilenanfang zu suchen,
  // weitere Durchläufe beginnen unmittelbar hinter dem vorigen Wort
  for (word_beg = line; ; word_beg = word_end) { 
    // Suche den Beginn des nächsten Wortes
    for ( ; !is_word_beg(*word_beg); ++word_beg) {
      if (word_beg == line_end) {
        // Wir sind am Zeilenende angelangt, kein Wort mehr gefunden:
        // Die Zeile ist fertig verarbeitet
        return;                    
      }
    }

    // Suche den ersten Buchstaben hinter diesem Wort
    for (word_end = word_beg + 1; is_in_word(*word_end); ++word_end) { }

    // Mach aus dem aktuellen Wort einen einzelnen String:
    // Schreib ein '\0' unmittelbar hinter das Wort (Pfui!)
    *word_end = '\0';
    // Spalte von word = Entfernung vom Zeilenanfang (gezählt ab 1, nicht ab 0)
    int col_nr = (word_beg - line) + 1;
    // Speichere das Wort und seine Position
    save_word(filename, line_nr, col_nr, word_beg);
  }
}

// Liest und verarbeitet den angegebenen File zeilenweise
// Bricht bei zu langen Zeilen mit Fehler ab!
void read_file(const char *filename)
{
  FILE *f = fopen(filename, "r");
  if (f == NULL) {
    fprintf(stderr, "%s: Can't open %s: %s\n", prog_name, filename,
            strerror(errno));
    exit(EXIT_FAILURE);
  }

  char line[LINE_LEN + 2];
  for (int line_nr = 1; fgets(line, sizeof (line), f); ++line_nr) {
    // Prüfung auf Zeilen länger LINE_LEN
    if ((strlen(line) == sizeof(line) - 1) &&
        (line[sizeof(line) - 2] != '\n')) {
      fprintf(stderr, "%s: Line too long on %s\n", prog_name, filename);
      exit(EXIT_FAILURE);
    }
    // Verarbeite alle Worte in line
    read_line(filename, line_nr, line);
  }

  if (ferror(f)) {
    fprintf(stderr, "%s: Can't read %s: %s\n", prog_name, filename,
            strerror(errno));
    exit(EXIT_FAILURE);
  }
  if (fclose(f) != 0) {
    fprintf(stderr, "%s: Can't close %s: %s\n", prog_name, filename,
            strerror(errno));
    exit(EXIT_FAILURE);
  }
}

// Gibt alle Positionen der Positionsliste des Wortes word aus
// Alle Positionen aus einem File werden in einer Zeile ausgegeben
// (mit dem Filenamen einmal am Zeilenanfang)
// Kommt eine Position aus einem neuen File, wird eine neue Zeile begonnen
void list_pos(const word_entry *word)
{
  const char *old_file = NULL; // Name des Files der vorigen Pos

  // Durchlaufe die Positionsliste
  for (const pos_entry *p = word->first_pos; p != NULL; p = p->next) {
    // Alle Pos-Einträge eines Files zeigen auf denselben Filenamen-String
    // ==> Pointer-Vergleich reicht aus, kein String-Vergleich nötig
    if (p->filename != old_file) {
      // Beginne neue Zeile mit neuem File
      old_file = p->filename;
      printf("\n%s:", p->filename);
    }
    printf(" %d/%d", p->line, p->column);
  }

  putchar('\n');
}

// Sucht das angegebene Wort word im Hashspeicher
// Gibt das Wort und seine Positionen (mittels list_pos)
// oder "nicht gefunden" aus
void process_word(const char *word)
{
  for (word_entry *w = hashtable[hash(word)]; w != NULL; w = w->next) {
    if (strcmp(w->text, word) == 0) {
      printf("*** %s:", word);
      list_pos(w);
      return;
    }
  }

  printf("*** %s: Not found! ***\n", word);
}

// Liest und verarbeitet den Input vom Terminal (ein Wort pro Zeile!)
void process_input(void)
{
  char line[LINE_LEN + 2];
  while (fgets(line, sizeof (line), stdin)) {
    char *p = strchr(line, '\n');
    if (p == NULL) {
      fprintf(stderr, "%s: Incomplete line on stdin\n", prog_name);
      exit(EXIT_FAILURE);
    }
    *p = '\0';   // '\n' entfernen
    process_word(line);
  }

  if (ferror(stdin)) {
    fprintf(stderr, "%s: Can't read stdin: %s\n", prog_name, strerror(errno));
    exit(EXIT_FAILURE);
  }
}

// Gibt Statistiken über die Hash-Verteilung aus
void statistics(void)
{
  int cnt[MAX_STAT_LEN] = { 0 }; // Anzahl der Listen mit Länge i
  int cnt_max = 0;  // Anzahl der Listen mit Länge >= MAX_STAT_LEN
  int total = 0;    // Gesamt-Anzahl aller Wortknoten
  int max_len = 0;  // Länge der längsten Liste

  for (int i = 0; i < HASH_PRIME; ++i) {  // Gehe alle Listen durch
    int len = 0;  // Länge der aktuellen Liste
    // Zähle die Wörter in der aktuellen Liste
    for (word_entry *w = hashtable[i]; w != NULL; w = w->next) {
      ++len;
      ++total;
    }
    if (len > max_len) {
      max_len = len;
    }
    if (len >= MAX_STAT_LEN) {
      ++cnt_max;
    } else {
      ++cnt[len];
    }
  }

  for (int i = 0; i < MAX_STAT_LEN; ++i) {
    if (cnt[i] > 0) {
      printf("%5d Listen mit Länge  %2d (%6.2f %%)\n", cnt[i], i,
             (cnt[i] * 100) / ((double) HASH_PRIME));
    }
  }
  if (cnt_max > 0) {
    printf("%5d Listen mit Länge >%2d (%6.2f %%), längste Liste %d\n", cnt_max,
           MAX_STAT_LEN, (cnt_max * 100) / ((double) HASH_PRIME), max_len);
  }
  printf("Insgesamt %d Knoten, mittlere Listenlänge ideal %5.3f, real %5.3f\n",
         total, total / ((double) HASH_PRIME), 
         total / ((double) (HASH_PRIME - cnt[0])));
}

// Liest und speichert alle Worte aus allen als Argument angegebenen Files
// Liest Worte vom Terminal und gibt deren gespeicherte Position aus
int main(int argc, const char *argv[])
{
  prog_name = argv[0];

  // Files einlesen und speichern
  if (argc == 1) {
    fprintf(stderr, "Usage: %s file ...\n", argv[0]);
    exit(EXIT_FAILURE);
  }
  for (int i = 1; i < argc; ++i) {
    read_file(argv[i]);
  }

  // Statistik ausgeben
  statistics();

  // Wörter von stdin einlesen und suchen
  process_input();

  exit(EXIT_SUCCESS);
}