// 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) == '_'))

// Typ eines Eintrags der Positionsliste
typedef struct _pos_entry {
/*** missing ***/
} pos_entry;

// Typ eines Eintrags der Wortliste
typedef struct _word_entry {
/*** missing ***/
} 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
/*** missing ***/

// 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)
{
/*** missing ***/
}

// 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)
{
/*** missing ***/
}

// 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)
{
/*** missing ***/
}

// Hängt die Position pos *hinten* an die (nichtleere!) Positionsliste
// des Wortknotens wort an
void add_pos(pos_entry *pos, word_entry *word)
{
/*** missing ***/
}

// 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)
{
/*** missing ***/
}

// 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)
{
/*** missing ***/
}

// 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)
{
/*** missing ***/
}

// 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)
{
/*** missing ***/
}

// 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);
}