SAI ||
Sommersemester 1997 ||
Systemnahe Software II ||
Übungen
<- Alle Module
Lösung zu Blatt 7 (Aufgabe 8): search.c
HTML-Parser für die Suchmaschine.
#include <stdio.h>
#include "stream.h"
#define OBRACK '<' /* opening and closing bracket */
#define CBRACK '>'
#define WSEP '+' /* Trenner in der Wortliste */
#define LSEP '@' /* Trenner in der Linkliste */
#define OCOMM "<!--" /* open comment */
#define CCOMM "-->" /* close comment */
#define MAXDEEP 5 /* maximale Rekursionstiefe */
#define MAXDOCS 200 /* soviele Dokumente maximal holen */
#define BUFLEN 1024 /* max. Laenge einer Zeile */
#define MAXHTTP 160 /* max. Laenge eines HTTP-Verweises */
extern char *strlwr(); /* Gross in Kleinschreibung */
extern char *strchr(); /* sucht Buchstaben im Text */
extern char *strrchr(); /* sucht letzt.Buchst. im Text */
extern char *strstr(); /* sucht String im String */
extern void *calloc(); /* KEINE Kornflakes ! */
/*
* Struktur fuer ein Suchwort
*/
typedef struct {
char *word; /* Zeiger auf das Wort */
int treffer; /* bereits im Dok. gefunden? */
} WLIST;
static char *docs[MAXDOCS]; /* Liste der besuchten Adressen */
static int docsp; /* nexter freier Listenplatz */
/*
* legt fuer jeden Suchbegriff einen Eintrag in der Struktur an
* das Array wird durch einen Dummy abgeschlossen
* Achtung: auf einer globalen Kopie arbeiten und das Original nicht aendern!
*/
static WLIST *initwlist(char *wlist)
{ char *copy = calloc(1, strlen(wlist)+1); /* Kopie der OriListe */
int count = 1; /* Anzahl Suchwoerter */
char *jogg;
WLIST *slist; /* Zeiger auf Suchstruktur */
if (!copy)
fprintf(stderr, "no more space ...\n"),
exit(1);
strcpy(copy, wlist); /* auf Kopie arbeiten ! */
copy = strlwr(copy); /* alles auf Kleinschreibung */
if (copy[strlen(copy)-1] == WSEP) /* Trenner am Ende ?? */
copy[strlen(copy)-1] = 0; /* dann loeschen! */
jogg = copy;
while (jogg = strchr(jogg, WSEP)) /* Anzahl der Woerter */
count++, jogg++;
/* Platz fr Suchstructs*/
if (!(slist = calloc(count+1, sizeof(WLIST))))
fprintf(stderr, "no more space ...\n"),
exit(1);
jogg = copy;
count = 0;
slist[0].word = copy; /* 1.Wort einhaengen */
while (jogg = strchr(jogg, WSEP)) /* ueber alle Woerter */
{ *jogg = 0; /* Trenner zu 0Byte */
count++;
slist[count].word = ++jogg; /* nextes Wort einhaengen*/
}
return slist;
}
/*
* sucht in der aktuellen Textzeile nach allen Suchwoertern
*/
static void lookforwords(char *text, WLIST *wl)
{ int i;
/* ueber alle Eintraege */
for (i=0; wl[i].word; i++)
wl[i].treffer += (strstr(text, wl[i].word) != NULL);
}
/*
* zerlegt eine gelesene Zeile in ihre Bestandteile: Text + Verweise
* sowie ggf. ein Rest, falls die Klammern noch nicht zu sind
*
* die Variable inbrack gibt an, ob in der letzten Zeile ein evtl. Verweis
* abgeschlossen war oder ob er sich bis zur aktuellen Zeile erstreckt
* Resultat der Funktion: Verweis in der Zeile abgeschlossen (0) oder nicht (1)
* in dem Buffer html stehen nachher saemtliche Links der Zeile durch LSEP
* getrennt drin (im Normalfall nur einer!)
*/
static int mkparts(char *buf, char *text, char *html, char *rest, int inbrack)
{ char *jogg = html;
for (; *buf; buf++) /* ueber jedes eingelesene Zeichen */
{ if (inbrack) /* innerhalb der Klammern? */
{ if (*buf == CBRACK) /* Klammer zu */
{ inbrack--;
if (!inbrack) /* alle Klammern zu ?? */
*jogg++ = LSEP; /* Trenner setzen */
}
else if (*buf==OBRACK) /* geschachtelte Klammer*/
inbrack++; /* z.B. Kommentar */
else /* normales Zeichen */
*jogg++ = *buf;
}
else /* ausserhalb der Klammer! */
{ if (*buf == OBRACK) /* Klammer auf */
inbrack++;
else if (*buf==CBRACK) /* geschachtelte Klammer*/
inbrack--;
else /* normales Zeichen */
*text++ = *buf;
}
}
*text = *jogg = 0; /* abschliessendes 0Byte */
if (inbrack) /* letzter Verweis nicht beendet*/
{ if (jogg = strrchr(html, LSEP)) /* suche nach Trenner */
{ strcpy(rest, jogg+1);
jogg[1] = 0;
}
else
{ strcpy(rest, html);
*html = 0;
}
}
return inbrack; /* Zeile bereits beendet ? */
}
/*
* schaut nach, ob das zu bearbeitende Dokument bereits da war bzw. die
* Liste der maximal bearbeitbaren Dokumente voll ist
*/
static int iscircle(char *adr)
{ int i;
if (docsp==MAXDOCS) /* kein neues Doku. mehr mgl. */
return 1;
for (i=0; i< docsp; i++)
if (!strcmp(adr, docs[i]))
return 1; /* war schon da */
docs[docsp] = calloc(1, strlen(adr)+1);
if (!docs[docsp])
fprintf(stderr, "no more space\n"),
exit(1);
strcpy(docs[docsp++], adr); /* Kopie anlegen && einhaengen */
return 0; /* war noch nicht da */
}
/*
* schaut sich ein HTML-Tag an; laesst nur <a href=".."> am Leben
* extrahiert dann die Zeichen in den Anfuehrungsstrichen
* falls mehrere hrefs kommen, sind die durch LSEP getrennt im String
* untergebracht (Achtung: am Ende der Liste steht IMMER ein LSEP)
* extrahiert von hinten her den Link; "verzehrendes Lesen"
*/
static char *getref(char *html)
{ char buf[BUFLEN]; /* Arbeitskopie wg. Klein- */
char *jogg; /* schreibung */
char *href;
char *hlp;
if (!*html) /* Liste ist leer */
return NULL;
if (html[strlen(html)-1] == LSEP) /* loesche letztes LSEP */
html[strlen(html)-1] = 0;
if (!*html) /* Liste ist JETZT leer */
return NULL;
if (!(jogg = strrchr(html, LSEP))) /* Trenner vor letztem */
{ int len = strlen(html)+2; /* KEIN Trenner mehr da */
strcpy(html+len, html); /* verdoppeln */
*html = 0; /* Loeschen: Suchende */
jogg = html+len; /* Zeiger auf Kopie */
}
else
*jogg++ = 0; /* Trenner loeschen */
strcpy(buf, jogg); /* kopieren und alles */
strlwr(buf); /* klein schreiben */
if (*buf != 'a' || buf[1] != ' ') /* faengt Tag mit "a " an?*/
{ *jogg = 0; /* Eintrag loeschen */
return getref(html); /* nein! suche nextes */
}
if (!(href = strstr(buf, "href="))) /* ist kein Link */
{ *jogg = 0; /* Eintrag loeschen */
return getref(html); /* weitersuchen */
}
href = jogg + (href - buf); /* Stelle im Original */
if (!(href = strchr(href, '"'))) /* wo ist " ? */
{ *jogg = 0;
return getref(html); /* weitersuchen */
}
if (!(hlp = strchr(href+1, '"'))) /* schliessendes " fehlt*/
{ *jogg = 0;
return getref(html); /* weitersuchen */
}
*hlp = 0; /* schliessendes " loeschen */
return href+1; /* uff: eigentliche Adresse */
}
/*
* entfernt \n und ggf. auch \r aus einem Buffer und setzt dorthin dann
* das Stringende
*/
static void delnl(char *s)
{
while (*s)
if (*s=='\r' || *s=='\n')
{ *s = 0;
return;
}
else
s++;
}
/*
* entfernt Kommentar aus der eingelesenen Zeile
* (evtl. ist die nachher leer)
* incomment gibt an, ob wir uns zur Zeit im Kommentar befinden ...
* Kommentare koennen nicht geschachtelt werden!
*/
static int delcomment(char *buf, int incomment)
{ char *jogg, *anf;
if (incomment) /* sind wir noch im Kommentar ? */
{ if (!(jogg = strstr(buf, CCOMM)))
{ *buf = 0; /* komplette Zeile ist Kommentar*/
return 1; /* kein Kommentarende */
}
strcpy(buf, jogg+3); /* Kommentar loeschen */
return delcomment(buf, 0); /* weiterer Kommentar? */
}
/* ausserhalb vom Kommentar */
if (!(anf = strstr(buf, OCOMM)))
return 0; /* kein Kommentaranfang */
/* Kommentar frisch entdeckt */
if (!(jogg = strstr(anf+3, CCOMM))) /* wieder zugemacht ? */
{ *anf = 0; /* nein! Kommentar loeschen */
return 1; /* bin im Kommentar drin */
}
/* Kommentar wieder zu ! */
strcpy(anf, jogg+3); /* Kommentar ueberschreiben */
return delcomment(buf, 0); /* evtl. weitere Kommentare ? */
}
/*
* schaut sich an, ob ein HREF eine http-Adresse enthaelt und kopiert diese
* dann in http
* die neue Adresse wird ggf. aus der alten zusammengesetzt
*/
static int ishttp(char *href, char *http, char *aktadr)
{ char *jogg = strchr(href, ':'); /* suche nach http: */
char *marke = strchr(href, '#');/* Verweis innnerhalb akt. Doku ?*/
char *hlp;
char domain[MAXHTTP]; /* aktueller Servername */
if (marke) /* nochmal Verweis gleiches Doku */
return 0;
strcpy(domain, aktadr); /* bastle Domain aus Namen */
if (!(hlp = strchr(domain, '/'))) /* alte Adresse nicht korrekt */
return 0;
hlp[1] = 0; /* habe Servername mit / am Ende */
if (jogg) /* Doppelpunkt drin ! */
{ if (strncmp(href, "http", 4)) /* KEIN Http-Verweis ? */
return 0; /* z.B. mailto: .... */
jogg ++; /* auf Pfadanfang */
}
else /* KEIN fuehrendes http: ... */
jogg = href; /* zeigt nun auf Pfadanfang */
if (!strncmp(jogg, "//", 2)) /* echte Adresse mit Server */
{ if (strncmp(domain, jogg+2, strlen(domain)))
return 0; /* neue Domain - geht nicht! */
else /* auf Pfadanfang posit. */
jogg = strchr(jogg+2, '/');
}
if (!jogg || *jogg != '/') /* relativ zum aktuellen PFAD */
{ strcpy(http, aktadr); /* alte Adresse kopieren */
if (hlp = strrchr(http, '/')) /* evtl. Seitennamen raus */
hlp[1] = 0; /* Ende nach letztem / */
}
else /* faengt mit / an */
{ strcpy(http, domain); /* nur Domain uebernehmen */
jogg++; /* sonst gibt es ein // */
}
strcat(http, jogg); /* neue Adresse an alte kleben */
strcpy(domain, http);
if (http[strlen(http)-1] != '/' && !strstr(strlwr(domain), ".htm"))
strcat(http, "/"); /* Slash am Ende vergessen ?! */
return 1;
}
/*
* eigentliche Suchfunktion, die ggf. auch rekursiv aufgerufen wird
* Abbruchbedingung: Verschachtelungstiefe bzw. das Dokument wurde bereits
* schon gescannt
*/
void search(char *wlist, char *adr, int rek)
{ STREAM *s;
char buf[BUFLEN]; /* akt. Zeile aus dem Stream */
char rest[BUFLEN]; /* evtl. Rest der letzten Zeile */
char text[BUFLEN]; /* nur Text */
char href[BUFLEN]; /* nur Verweise */
char http[MAXHTTP]; /* http-Adresse fuer Rekursion */
char *jogg;
WLIST *treffer; /* Checkliste fuer Suchwoerter */
int i;
int res;
int incomment = 0; /* Zustand: in Kommentar */
int inbrack = 0; /* Zustand: innerhalb/ausserhalb*/
/* der <> Klammern */
if (rek >MAXDEEP || iscircle(adr))/* Abbruch der Rekursion */
return;
fprintf(stderr, "> searching %s\n", adr);
if (!(s = openstream(adr))) /* Leseverbindung oeffnen */
return;
treffer = initwlist(wlist); /* frische Suchliste anfertigen */
/* noetig fuer Rekursion ! */
*rest = 0; /* am Anfang kein Uebertrag */
/* ueber alle Textzeilen */
while (getstream(buf, sizeof(buf), s)) /* Zeile einlesen */
{ delnl(buf); /* entferne \r \n */
if (*rest) /* Zeilenrest vom letzten Mal ? */
{ if (strlen(rest)+strlen(buf) >BUFLEN)
break; /* emergency break */
strcat(rest, buf); /* neuen Text anhaengen */
strcpy(buf, rest);
*rest = 0;
}
/* ggf. Kommentar entfernen */
incomment = delcomment(buf, incomment);
/* zerlege Zeile in Text, Verweise und ggf. Rest */
inbrack = mkparts(buf, text, href, rest, inbrack);
lookforwords(strlwr(text), treffer); /* suche nach Wort */
while (jogg = getref(href))/* Verweisliste abarbeiten */
if (ishttp(jogg, http, adr)) /* Adresse basteln */
search(wlist, http, rek+1);
}
closestream(s);
/* alle Worte im Text gefunden ? */
for (res = 1, i=0; treffer[i].word; i++)
res = res && treffer[i].treffer;
free(treffer); /* Trefferliste freigeben */
if (res) /* alle Begriffe gefunden ?? */
/*
printf("<a href=\"http://%s\">/%s</a><br>\n", adr,adr); /* Link ausgeben */
printf("found: %s\n", adr); /* Adresse ausgeben */
}
<- Alle Module
SAI ||
Sommersemester 1997 ||
Systemnahe Software II ||
Übungen
Matthias Grabert, Juli 1997