Capitolul 6.6. Cautare in tabele

In aceasta sectiune vom da continutul unui pachet de cautare in tabel ca o ilustrare a mai multor aspecte legate de structuri. Amcest pachet este tipic pentru modul de explorare a unui tabel de simboluri pentru rutinele de management ale unui macroprocesor. De exemplu sa consideram declaratia din C,
"#define". Cind o linie ca

#define YES 1

este luata in considerare, numele YES si textul corespunzator 1 sint memorate intr-un tabel. Mai tirziu, cind numele YES apare intr- declaratie ca

inword = YES;

trebuie inlocuit cu 1.

Exista doua rutine majore care manipuleaza numele si textele de inlocuire corespunzatoare. "install(s, t)" inregistreaza numele "s" si textul de inlocuire "t" intr-o tabela; "s" si"t" sint siruri de caractere. "lookup(s)" cauta numele "s" intr-o tabela si returneaza un pointer la locul unde afost gasit ori NULL daca nu a fost gasit.

Algoritmul care se utilizeaza se bazeaza pe o cautare fragmentara "hash" un nume care se introduce este convertit intr-un intreg pozitiv care apoi este utilizat ca index intr-un tabloude pointeri. Un element al tablului pointeaza pe inceputul unui lant de balncuri care descriiu avind respectiva valoare de fragment ("hash"). Acesta este NULL daca nici un nume nu corespunde acestei valori.

Un bloc din lant este o structura care contine: pointeri, la nume, textul de inlocuire si urmatorul bloc din lant. Daca pointerul pentru urmatorul bloc este nul marcheaza sfirsitul lantului de blocuri.

struct nlist { /* basic table entry */
char *name;
char *def;
struct nlist *next; /* next entry in chain */
};

Tabloul de poiunteri este:

#define HASHSIZE 100
static struct nlist *hashtab[HASHSIZE]; /* pointer table */

Functia de fragmentare ("hashing"), care este utilizata de ambele rutine "lookup" si "install", aduna valorile carcterelor din sirul nume si formeaza restul modulo dimensiunea tabloului. (Aceasta nu este cel mai bun algoritm posibil, darare meritul simplitatii. )

hash(s) /* form hash value for string s */
char *s;
{
int hashval;
for (hashval = 0; *s != '0'
hashval += *s++;
return(hashval % HASHSIZE);
}

Procesul de fragmentare ("hashing") produce un index de cautare in "hashtab"; sirul de carctere cautat se va gasi intr-un bloc din sirul de blocuri a carui inceput este pointat de elementul din tabelul "hashtab". Cautarea este efectuata de rutina "lookup". Dca "lookup" gaseste in "hashtab" intrarea deja prezenta, returneaza un pointer; daca nu, returneaza NULL.

struct nlist *lookup(s) /* look for s in hashtab */
char *s
{
struct nlist *up
for (up = hashtab[hash(s)]; up != NULL; up = up->next)
if (strcmp(s, up->name) == 0)
return(up); /*found it */
return(NULL); /* not found */

Rutina "install" foloseste "lookup" pentru a determina care dintre numele de instalat sint deja prezente; daca nu, o noua definire trebuie sa succeada uneia vechi. Altfel spus, o intrare complect noua este creeata. "install" returneza NULL daca dintr-un motiv oarecare nu mai este loc pentru o noua intrare.

struct nlist *install(name, def) /*put(name, def) */
char *name, *def; /* in hashtab */
{
struct nlist *np, *lookup();
char *strsave(), *alloc();
int hashval;
if ((np = lookup(name)) == NULL) { /* not found */
np = (struct nlist *) alloc(sizeof(*np));
if (np == NULL)
return(NULL);
if ((np->name = strsave(name)) == NULL)
return(NULL);
hashval = hash(np->name);
np->next = hashtab[hashval];
hashtab[hashval] = np;
} else /* already there */
free(np->def); /*free previous definition */
if ((np->def = strsave(def)) == NULL
return(NULL);
return(np);
}

"strsave" copiaza sirul furnizat de catre argumentul sasu intr_un loc obtinut cu un apel la functia "alloc". Am prezentat codul in capitolul 5 Deoarece apelurile la "alloc" si "free" pot sa apara in orice ordine si deoarece aici aliniamentul conteaza, versiunea simpla a "alloc" de la capitolul 5, nu este adecvata aici vedeti capitolele 7 si 8.


Exercitiul 6.7. Scrieti o rutina care sa scoata un nume si definitia dintr-o tabela mentinuta cu "lookup" si "install".

Exercitiul 6.8. Implementati o versiune simpla a procesorului "#define" utilizabila in programe C, folosind rutinele din aceasta sectiune. Puteti gasi de ajutor si "getch" si "ungetch".