ANSI C 6

6 STRUKTURY

Ogniwo łańcucha jest strukturą zawierającą wskaźniki do nazwy, do zastępującego ją tekstu oraz do następnego opisu w łańcuchu. Zerowy wskaźnik następnego ogniwa oznacza koniec listy.

struct nlist { /* ogniwo łańcucha */

struct nlist *next; /* następne ogniwo */ char *name; /* definiowana nazwa */ char *defn;    /* zastępujący ją tekst */

};

Tablica wskaźników ma postać #define HASHSIZE 101

static struct nlist *hashtab[HASHSIZEj; /* tablica wskaźników */

Funkcja rozpraszająca, używana przez funkcje lookup i install, dodaje wartość kolejnego znaku tekstu do wymieszanej kombinacji poprzednich znaków, dając w wyniku resztę z dzielenia (modulo) tak obliczonej wartości przez rozmiar tablicy. Ta funkcja nie jest najlepszą z funkcji rozpraszających, ma jednak tę zaletę, że jest krótka i skuteczna.

/* hash: daj wartość rozproszenia dla tekstu s */ unsigned hash(char *s)

{

unsigned hashval;

for (hashval = 0; *s != ’\0’; s-h-) hashval = *s + 31 * hashval; return hashval % HASHSIZE;

}

Arytmetyka na liczbach bez znaku (unsigned) daje gwarancję, że obliczona wartość rozproszenia jest liczbą nieujemną.

Wynikiem rozproszenia jest indeks początkowego wskaźnika w tablicy hashtab; jeśli tylko dany tekst jest gdziekolwiek zapisany, znajdzie się on w w łańcuchu opisów rozpoczynającym się od tego miejsca. Przeszukiwania dokonuje funkcja lookup. Jeże' li dany tekst już kiedyś wystąpił, to funkcja zwraca wskaźnik do jego opisu, w prze-ciwnym przypadku zwraca NULL.

6.6 PRZEGLĄDANIE TABLIC _

I* lookup: szukaj tekstu z s w tablicy hashtab */ struct nlist *lookup(char *s)

{

struct nlist *np;

for (np = hashtab [hash(s)]; np != NULL; np = np->next) if (strcmp(s, np->name) == 0) return np; /* znaleziono */ return NULL; /* nie znaleziono */

}

Pętla for w funkcji lookup jest standardowym zwrotem języka C, służącym do maszerowania wzdłuż listy połączonych ze sobą obiektów:

for (ptr = head; ptr != NULL; ptr = ptr->next)

• • •

Funkcja install używa funkcji lookup do rozstrzygania, czy wprowadzana nazwa już wystąpiła; jeżeli tak, to nowa definicja musi zastąpić starą. W przeciwnym przypadku jest tworzone nowe ogniwo łańcucha.

struct nlist *lookup(char *); char *strdup(char *);

/* install: wstaw (name, defn) do tablicy hashtab */ struct nlist *install(char *name, char *defn)

{

struct nlist *np; unsigned hashval;

if ((np = lookup(name)) == NULL) {    /* nie znaleziono */

np = (struct nlist *) malloc(sizeof(*np)); if (np == NULL || (np->name = strdup(name)) == NULL) return NULL; hashval = hash(name); np->next = hashtab[hashvalj; hashtab[hashvall = np;

} else /* już była */

free((void *) np->defn); /* zwolnij starą definicję */ if ((np->defn = strdup(defn)) == NULL) return NULL; return np;

}

195