O structura este o colectie de una sau mai multe variabile, de acelasi tip sau de tipuri diferite, grupate impreuna sub un singur nume pentru a putea fi tratate impreuna (in alte limbaje, structurile se numesc articole). t1q1qc
Structurile ajuta la organizarea datelor complicate, in special in programele mari, deoarece permit unui grup de variabile legate sa fie tratate ca o singura entitate. Vom ilustra in acest capitol modul de utilizare a structurilor.

10.1. Elemente de baza

Sa revenim asupra rutinei de conversie a datei prezentata in capitolul 9.
O data consta din zi, luna si an, eventual numarul zilei din an si numele lunii. Aceste cinci variabile pot fi grupate intr-o singura structura astfel:

struct date A int day; int month; int year; int yearday; char mon_namea4i;
S;

Cuvintul cheie struct introduce o declaratie de structura care este o lista de declaratii inchise in acolade.
Cuvintul struct poate fi urmat optional de un nume, numit marcaj de structura sau eticheta de structura, cum este in exemplul nostru numele date. Acest marcaj denumeste acest tip de structura si poate fi folosit in continuare ca o prescurtare pentru declaratia de structura detaliata careia ii este asociat.
Elementele sau variabilele mentionate intr-o structura se numesc membri ai structurii. Un membru al structurii sau o eticheta si o variabila oarecare, nemembru, pot avea acelasi nume fara a genera conflicte, deoarece ele vor fi intotdeauna deosebite una de alta din context.
Acolada dreapta care incheie o lista de membri ai unei structuri poate fi urmata de o lista de variabile, la fel ca si in cazul tipurilor de baza. De exemplu: struct A. . .S x,y,z; este din punct de vedere sintactic analog cu: int x,y,z;
in sensul ca fiecare declaratie declara pe x, y si z ca variabile de tipul numit (structura in primul caz si intreg in al doilea) si cauzeaza alocarea de spatiu pentru ele.
O declaratie de structura care nu este urmata de o lista de variabile nu aloca memorie; ea descrie numai un sablon, o forma de structura. Daca structura este marcata sau etichetata, atunci marcajul ei poate fi folosit mai tirziu pentru definirea unor alte variabile de tip structura, cu acelasi sablon ca structura marcata. De exemplu, fiind data declaratia: struct date d; ea defineste variabila d, ca o structura de acelasi fel (sablon) ca structura date.
O structura externa sau statica poate fi initializata, atasind dupa definitia ei o lista de initializatori pentru componente, de exemplu: struct date d = A4,7,1984,185,"iulie"S;
Un membru al unei structuri este referit printr-o expresie de forma: nume-structura.membru
in care operatorul membru de structura ’.’ leaga numele membrului de numele structurii. Ca exemplu fie atribuirea:

leap = (d.year%4==0) && (d.year%100!=0)
|| (d.year%400==0);

sau verificarea numelui lunii: if (strcmp(d.mon_name,"august")==0) ...

Structurile pot fi imbricate; o inregistrare de stat de plata, de exemplu, poate fi de urmatoarea forma:

struct person A char nameaNAMESIZEi; char addressaADRSIZEi; long zipcode; long ss_number; double salary; struct date birthdate; struct date hiredate;
S;

Structura person contine doua structuri de sablon date. Declaratia: struct person emp; defineste si aloca o structura cu numele emp de acelasi sablon ca si person. Atunci: emp.birthdate.month se refera la luna de nastere. Operatorul de membru de structura ’.’ este asociativ de la stinga la dreapta.

10.2. Structuri si functii

Exista un numar de restrictii asupra structurilor in limbajul C. Singurele operatii care se pot aplica unei structuri sint accesul la un membru al structurii si considerarea adresei ei cu ajutorul operatorului &. Acest lucru implica faptul ca structurile nu pot fi atribuite sau copiate ca entitati si ca ele nu pot fi transmise ca argumente la functii si nici returnate din functii. Structurile de clasa automatic, ca si masivele de aceeasi clasa, nu pot fi initializate; pot fi initializate numai structurile externe si statice, regulile de initializare fiind aceleasi ca pentru masive.
Pointerii la structuri nu se supun insa acestor restrictii, motiv pentru care structurile si functiile pot coexista si conlucra prin intermediul pointerilor.
Ca un exemplu, sa rescriem programul de conversie a datei, care calculeaza ziua anului, din luna si zi.

day_of_year(struct date *pd) A
/* calculul zilei anului */ int i, day, leap; day = pd->day; leap = (pd->year%4==0) &&
(pd->year%100!==0) ||
(pd->year%400==0); for (i=1; i<pd->month; i++) day += day_tabaleapiaii; return day;
S

Declaratia: struct date * pd; indica faptul ca pd este un pointer la o structura de sablonul lui date. Notatia: pd->year indica faptul ca se refera membrul "year" al acestei structuri. In general, daca p este un pointer la o structura p->membru-structura se refera la un membru particular (operatorul ’->’ se formeaza din semnul minus urmat de semnul mai mare).
Deoarece pd este pointer la o structura, membrul year poate fi de asemenea referit prin:
(*pd).year
Notatia "->" se impune ca un mod convenabil de prescurtare. In notatia (*pd).year, parantezele sint necesare deoarece precedenta operatorului membru de structura ’.’ este mai mare decit cea a operatorului *.
Ambii operatori ’.’ si ’->’ sint asociativi de la stinga la dreapta, astfel incit: p->q->membru emp.birthdate.month sint de fapt:
(p->q)->membru
(emp.birthdate).month
Operatorii ’->’ si ’.’ ai structurilor, impreuna cu () pentru listele de argumente si ai pentru indexare se gasesc in virful listei de precedenta (vezi sectiunea 4.16), fiind din acest punct de vedere foarte apropiati. Astfel, fiind data declaratia: struct A int x; int *y;S *p; unde p este un pointer la o structura, atunci expresia:
++p->x incrementeaza pe x, nu pointerul p, deoarece operatorul ’->’ are o precedenta mai mare decit ’++’. Parantezele pot fi folosite pentru a modifica ordinea operatorilor data de precedenta. Astfel:
(++p)->x incrementeaza mai intii pe p si apoi acceseaza elementul x, din structura nou pointata.
In expresia (p++)->x se acceseaza mai intii x, apoi se incrementeaza pointerul p.
In mod analog, *p->y indica continutul adresei pe care o indica y. Expresia *p->y++ acceseaza mai intii ceea ce indica y si apoi incrementeaza pe y. Expresia (*p->y)++ incrementeaza ceea ce indica y. Expresia *p++->y acceseaza ceea ce indica y si apoi incrementeaza pointerul p.

10.3. Masive de structuri

Structurile sint in mod special utile pentru tratarea masivelor de variabile legate prin context. Pentru exemplificare vom considera un program care numara intrarile fiecarui cuvint cheie dintr-un text. Pentru aceasta avem nevoie de un masiv de siruri de caractere, pentru pastrarea numelor cuvintelor cheie si un masiv de intregi pentru a memora numarul aparitiilor. O posibilitate este de a folosi doua masive paralele keyword si keycount declarate prin: char *keywordaNKEYSi; int keycountaNKEYSi; respectiv unul de pointeri la siruri de caractere si celalalt de intregi. Fiecarui cuvint cheie ii corespunde perechea: char *keyword; int keycount; astfel incit putem considera cele doua masive ca fiind un masiv de perechi. Atunci, declaratia de structura:

struct key A char *keyword; int keycount;
S keytabaNKEYSi;

defineste un masiv keytab de structuri de acest tip si aloca memorie pentru ele. Fiecare element al masivului keytab este o structura de acelasi sablon ca si structura key.
Definitia masivului keytab poate fi scrisa si sub forma:

struct key A char *keyword; int keycount;
S; struct key keytabaNKEYSi;

Deoarece masivul de structuri keytab contine, in cazul nostru, o multime constanta de cuvinte cheie, este mai usor de initializat o data pentru totdeauna chiar in locul unde este definit. Initializarea structurilor este o operatie analoaga cu initializarea unui masiv in sensul ca definitia este urmata de o lista de initializatori inchisi in acolade.
Atunci initializarea masivului de structuri keytab va fi urmatoarea:

struct key A char * keyword; int keycount;
S keytabai = A
"break",0,
"case",0,
"char",0,
/* ... */
"while",0S;

Initializatorii sint perechi care corespund la membrii structurii. Initializarea ar putea fi facuta si incluzind initializatorii fiecarei structuri din masiv in acolade ca in:
A"break",0S,A"case",0S.... dar parantezele interioare nu sint necesare daca initializatorii sint variabile simple sau siruri de caractere si daca toti initializatorii sint prezenti.
Compilatorul va calcula, pe baza initializatorilor, dimensiunea masivului de structuri keytab motiv pentru care, la initializare, nu este necesara indicarea dimensiunii masivului.
Programul de numarare a cuvintelor cheie incepe cu definirea masivului de structuri keytab. Rutina principala main citeste textul de la intrare prin apel repetat la o functie getword, care extrage din intrare cite un cuvint la un apel. Fiecare cuvint este apoi cautat in tabelul keytab cu ajutorul unei functii de cautare binary, descrisa in sectiunea 7.5. Lista cuvintelor cheie trebuie sa fie in ordine crescatoare pentru ca functia binary sa lucreze corect. Daca cuvintul cercetat este un cuvint cheie atunci functia binary returneaza numarul de ordine al cuvintului in tabelul cuvintelor cheie, altfel returneaza ?1.

#define MAXWORD 20

binary(char *word, struct key tabai, int n) A int low,high,mid,cond; low = 0; high = n - 1;
while (low<=high) A mid =(low + high) / 2; if (
(cond=strcmp(word,tabamidi.keyword))
<0) high = mid - 1; else if (cond>0) low = mid + 1; else return mid;
S return -1;
S

main() A /* numara cuvintele cheie */ int n,t; char wordaMAXWORDi;
while ((t=getword(word,MAXWORD))!=EOF) if (t==LETTER) if (
(n=binary(word,keytab,NKEYS))
>=0) keytabani.keycount++; for (n=0; n<NKEYS; n++) if (keytabani.keycount>0) printf("%4d %s\n", keytabani.keycount, keytabani.keyword);
S

Inainte de a scrie functia getword este suficient sa spunem ca ea returneaza constanta simbolica LETTER de fiecare data cind gaseste un cuvint in textul de intrare si copiaza cuvintul in primul ei argument.
Cantitatea NKEYS este numarul cuvintelor cheie din keytab (dimensiunea masivului de structuri). Desi putem calcula acest numar manual, este mai simplu si mai sigur s-o facem cu calculatorul, mai ales daca lista cuvintelor cheie este supusa modificarilor. O posibilitate de a calcula NKEYS cu calculatorul este de a termina lista initializatorilor cu un pointer NULL si apoi prin ciclare pe keytab sa detectam sfirsitul lui. Acest lucru este mai mult decit necesar deoarece dimensiunea masivului de structuri este perfect determinata in momentul compilarii. Numarul de intrari se determina impartind dimensiunea masivului la dimensiunea structurii key.
Operatorul sizeof descris in sectiunea 4.2 furnizeaza dimensiunea in octeti a argumentului sau.
In cazul nostru, numarul cuvintelor cheie este dimensiunea masivului keytab impartita la dimensiunea unui element de masiv. Acest calcul este facut intr-o linie #define pentru a da o valoare identificatorului NKEYS:
#define NKEYS (sizeof(keytab) / sizeof(struct key))
Sa revenim acum la functia getword. Programul pe care-l vom da pentru aceasta functie este mai general decit este necesar in aplicatia noastra, dar nu este mult mai complicat.
Functia getword citeste cuvintul urmator din textul de intrare, printr-un cuvint intelegindu-se fie un sir de litere si cifre, cu primul caracter litera, fie un singur caracter. Functia returneaza constanta simbolica LETTER daca a gasit un cuvint, EOF daca a detectat sfirsitul fisierului sau caracterul insusi, daca el nu a fost alfabetic.

getword(char *w, int lim) A /* citeste un cuvint */ int t;
while (--lim>0) A t = type(*w++=getchar()); if (t==EOF) return EOF; if (t!=LETTER && t!=DIGIT) break;
S
*(w-1) = '\0'; return LETTER;
S

Functia getword apeleaza functia type pentru identificarea tipului fiecarui caracter citit la intrare cu ajutorul functiei getchar. Versiunea functiei type pentru caractere ASCII este:

type(int c) A /* returneaza tipul caracterului */ if (c>='a' && c<='z' || c>='A' && c<='Z') return LETTER; if (c>='0' && c<='9') return DIGIT; return c;
S

Constantele simbolice LETTER si DIGIT pot avea orice valoare care nu vine in contradictie cu caracterele nealfabetice si EOF. Valori posibile pot fi:
#define LETTER 'a'
#define DIGIT '0'

10.4. Pointeri la structuri

Pentru a ilustra modul de corelare dintre pointeri si masivele de structuri, sa rescriem programul de numarare a cuvintelor cheie dintr-un text, de data aceasta folosind pointeri, in loc de indici de masiv.

Declaratia externa a masivului de structuri keytab nu necesita modificari, in timp ce functiile main si binary da. Prezentam, in continuare, aceste functii modificate.

#define MAXWORD 20

struct key *binary(char *word, struct key tabai, int n) A
/* cauta cuvint */ int cond; struct key * low; struct key *high; struct key *mid; low = &taba0i; high = &taban-1i;
while (low<=high) A mid = low + (high-low) / 2; if ((cond=strcmp(word,mid->keyword))<0) high = mid - 1; else if (cond>0) low = mid + 1; else return mid;
S return NULL;
S

main() A /* numara cuvintele cheie, versiune cu pointeri */ int t; char wordaMAXWORDi; struct key *binary(), *p;
while ((t=getword(word.MAXWORD))!=EOF) if (t==LETTER) if ((p=binary(word,keytab,NKEYS))
!= NULL) p->keycount++; for (p=keytab; p<keytab+NKEYS; p++) if (p->keycount>0) printf("%4d %s\n",p->keycount, p->keyword);
S

Sa observam citeva lucruri importante in acest exemplu. In primul rind, declaratia functiei binary trebuie sa indice ca ea returneaza un pointer la o structura de acelasi sablon cu structura key, in loc de un intreg. Acest lucru este declarat atit in functia principala main cit si in functia binary. Daca binary gaseste un cuvint in structura key, atunci returneaza un pointer la el; daca nu-1 gaseste, returneaza NULL. In functie de aceste doua valori returnate, functia main semnaleaza gasirea cuvintului prin incrementarea cimpului keycount corespunzator cuvintului sau citeste urmatorul cuvint.
In al doilea rind, toate operatiile de acces la elementele masivului de structuri keytab se fac prin intermediul pointerilor. Acest lucru determina o modificare semnificativa in functia binary. Calculul elementului mijlociu nu se mai poate face simplu prin: mid = (low + high) / 2 deoarece adunarea a doi pointeri este o operatie ilegala, nedefinita. Aceasta instructiune trebuie modificata in: mid = low + (high-low) / 2 care face ca mid sa pointeze elementul de la jumatatea distantei dintre low si high.
Sa mai observam initializarea pointerilor low si high, care este perfect legala, deoarece este posibila initializarea unui pointer cu o adresa a unui element deja definit.
In functia main avem urmatorul ciclu: for(p=keytab; p<keytab+NKEYS; p++)...
Daca p este un pointer la un masiv de structuri, orice operatie asupra lui p tine cont de dimensiunea unei structuri, astfel incit p++ incrementeaza pointerul p la urmatoarea structura din masiv, adunind la p dimensiunea corespunzatoare a unei structuri. Acest lucru nu inseamna ca dimensiunea structurii este egala cu suma dimensiunilor membrilor ei deoarece din cerinte de aliniere a unor membri se pot genera „goluri” intr-o structura.
In sfirsit, cind o functie returneaza un tip complicat si are o lista complicata de argumente, ca in: struct key *binary(char *word, struct key tab, int n) functia poate fi mai greu vizibila si detectabila cu un editor de texte. Din acest motiv, se poate opta si pentru urmatoarea forma: struct key *binary(word,tab,n) char *word; struct key tab; int n; unde inainte de acolada de deschidere se precizeaza tipul fiecarui parametru.
Alegeti forma care va convine si care vi se pare mai sugestiva.

10.5. Structuri auto-referite

Sa consideram problema mai generala, a numarului aparitiilor tuturor cuvintelor dintr-un text de intrare. Deoarece lista cuvintelor nu este cunoscuta dinainte, n-o putem sorta folosind algoritmul de cautare binara, ca in paragraful precedent. Nu putem utiliza nici o cautare liniara pentru fiecare cuvint, pe masura aparitiei lui pentru a vedea daca a mai fost prezent sau nu, pentru ca timpul de executie al programelor ar creste patratic cu numarul cuvintelor de la intrare.
Un mod de a organiza datele pentru a lucra eficient cu o lista de cuvinte arbitrare este de a pastra multimea de cuvinte, tot timpul sortata, plasind fiecare nou cuvint din intrare pe o pozitie corespunzatoare, relativ la intrarile anterioare. Daca am realiza acest lucru prin deplasarea cuvintelor intr-un masiv liniar, programul ar dura, de asemenea, foarte mult. De aceea, pentru rezolvarea eficienta a acestei probleme vom folosi o structura de date numita arbore binar.
Fiecare nod al arborelui va reprezenta un cuvint distinct din intrare si va contine urmatoarea informatie:
- un pointer la cuvint;
- un contor pentru numarul de aparitii;
- un pointer la descendentul sting al cuvintului;
- un pointer la descendentul drept al cuvintului. Nici un nod al arborelui nu va avea mai mult decit doi descendenti dar poate avea un descendent sau chiar nici unul.
Arborele se construieste astfel incit pentru orice nod, sub-arborele sting al sau contine numai cuvintele care sint mai mici decit cuvintul din nod, iar sub-arborele drept contine numai cuvinte, care sint mai mari decit cuvintul din nod, compararea facindu-se din punct de vedere lexicografic.
Pentru a sti daca un cuvint nou din intrare exista deja in arbore se porneste de la nodul radacina si se compara noul cuvint cu cuvintul memorat in nodul radacina. Daca ele coincid se incrementeaza contorul de numarare a aparitiilor pentru nodul radacina si se va citi un nou cuvint din intrare.
Daca noul cuvint din intrare este mai mic decit cuvintul memorat in nodul radacina, cautarea continua cu descendentul sting, altfel se investigheaza descendentul drept. Daca nu exista nici un descendent pe directia ceruta, noul cuvint nu exista in arbore si va fi inserat pe pozitia descendentului corespunzator. Se observa ca acest proces de cautare este recursiv, deoarece cautarea din fiecare nod utilizeaza o cautare intr-unul dintre descendentii sai.
Prin urmare se impune de la sine ca rutinele de inserare in arbore si de imprimare sa fie recursive.
Revenind la descrierea unui nod, el apare ca fiind o structura cu patru componente:

struct tnode A /* nodul de baza */ char *word; /* pointer la cuvint */ int count; /* numarator de aparitii */ struct tnode *left; /* descendent sting */ struct tnode *right; /* descendent drept */
S;

Aceasta declaratie „recursiva” a unui nod este perfect legala, deoarece o structura nu poate contine ca si componenta o intrare a ei insasi dar poate contine un pointer la o structura de acelasi sablon cu ea.
Declaratia: struct tnode *left; declara pe left ca fiind un pointer la structura (nod) si nu o structura insasi.
In program vom folosi rutinele getword, pentru citirea unui cuvint din intrare, alloc pentru rezervarea de spatiu necesar memorarii unui cuvint si alte citeva rutine pe care le cunoastem deja. Rutina principala main citeste prin intermediul rutinei getword un cuvint, si il plaseaza in arbore prin rutina tree.

#define MAXWORD 20

main() A /* contorizare aparitii cuvinte */ struct tnode *root, *tree(); char wordaMAXWORDi; int t; root = NULL;
while ((t=getword(word,MAXWORD))!=EOF) if (t==LETTER) root = tree(root,word); treeprint(root);
S

Rutina main gestioneaza fiecare cuvint din intrare incepind cu cel mai inalt nivel al arborelui (radacina). La fiecare pas, cuvintul din intrare este comparat cu cuvintul asociat radacinii si este apoi transmis in jos, fie descendentului sting, fie celui drept, printr-un apel recursiv la rutina tree. In acest proces, cuvintul fie exista deja, undeva in arbore, caz in care contorul lui de numarare a aparitiilor se incrementeaza, fie cautarea continua pina la intilnirea unui pointer NULL, caz in care nodul trebuie creat si adaugat arborelui. Cind se creeaza un nod nou, rutina tree returneaza un pointer la el, care apoi este introdus in nodul de origine (adica in nodul al carui descendent este noul nod) in cimpul left sau right dupa cum noul cuvint este mai mic sau mai mare fata de cuvintul origine. Rutina tree, care returneaza un pointer la o structura de sablon tnode are urmatorul cod:

struct tnode *tree(struct tnode *p, char *w) A /* introduce cuvintul w in nodul p */ struct tnode *talloc(int n); char *strsav(char *s); int cond; if (p==NULL) A /* a sosit un nou cuvint */ p = talloc(); /* creeaza un nod nou */ p->word = strsav(w); p->count = 1; p->left = p->right = NULL;
S else if ((cond=strcmp(w,p->word))==0) p->count++; else if (cond<0) /* noul cuvint mai mic */ p->left = tree(p->left,w); else /* noul cuvint mai mare */ p->right = tree(p->right,w); return p;
S

Memoria pentru noul nod se aloca de catre rutina talloc, care este o adaptare a rutinei alloc, pe care am vazut-o deja. Ea returneaza un pointer la un spatiu liber, in care se poate inscrie noul nod al arborelui. Vom discuta rutina talloc mai tirziu. Noul cuvint se copiaza in acest spatiu cu ajutorul rutinei strsav, care returneaza un pointer la inceputul cuvintului, contorul de aparitii se initializeaza la 1 si pointerii catre cei doi descendenti se fac NULL. Aceasta parte de cod se executa numai cind se adauga un nou nod.
Rutina treeprint tipareste arborele astfel incit pentru fiecare nod se imprima sub-arborele lui sting, adica toate cuvintele mai mici decit cuvintul curent, apoi cuvintul curent si la sfirsit sub-arborele drept, adica toate cuvintele mai mari decit cuvintul curent. Rutina treeprint este una din cele mai tipice rutine recursive.

treeprint(struct tnode *p) A
/* tipareste arborele p recursiv */ if (p!=NULL) A treeprint(p->left); printf("%5d %s\n",p->count,p->word); treeprint(p->right);
S
S

Este important de retinut faptul ca in algoritmul de cautare in arbore, pentru a ajunge la un anumit nod, se parcurg toate nodurile precedente, pe ramura respectiva (stinga sau dreapta), incepind intotdeauna cu nodul radacina. Dupa fiecare iesire din rutina tree, din cauza recursivitatii, se parcurge acelasi drum, de data aceasta de la nodul gasit spre radacina arborelui, refacindu-se toti pointerii drumului parcurs.
Daca considerati ca nu ati inteles suficient de bine recursivitatea, desenati-va un arbore si imprimati-l cu ajutorul rutinei treeprint, avind grija sa memorati fiecare iesire din tree si treeprint.
O observatie legata de acest exemplu: daca arborele este „nebalansat“, adica cuvintele nu sosesc in ordine aleatoare din punct de vedere lexicografic, atunci timpul de executie al programului poate deveni foarte mare. Cazul limita in acest sens este acela in care cuvintele de la intrare sint deja in ordine, (crescatoare sau descrescatoare), caz in care programul nostru simuleaza o cautare liniara intr-un mod destul de costisitor.

Sa ne oprim putin asupra alocarii de memorie. Cu toate ca se aloca diferite tipuri de obiecte, este de preferat sa existe un singur alocator de memorie intr-un program. Relativ la acest alocator de memorie se pun doua probleme: in primul rind cum poate satisface el conditiile de aliniere ale obiectelor de un anumit tip (de exemplu intregii trebuie alocati la adrese pare); in al doilea rind cum se poate declara ca alocatorul returneaza pointeri la tipuri diferite de obiecte.
Cerintele de aliniere pot fi in general rezolvate cu usurinta pe seama unui spatiu care se pierde, dar care este nesemnificativ ca dimensiune. De exemplu, alocatorul alloc returneaza totdeauna un pointer la o adresa para. In cazul in care cererea de alocare poate fi satisfacuta si de o adresa impara (pentru siruri de caractere, de exemplu) se pierde un caracter.
In ceea ce priveste declararea tipului alocatorului alloc (adica a tipului de obiect pe care il indica pointerul returnat de alloc), un foarte bun procedeu in limbajul C este de a declara ca functia alloc returneaza un pointer la char si apoi sa convertim explicit acest pointer la tipul dorit printr-un cast. Astfel daca p este declarat in forma: char *p; atunci:
(struct tnode *)p; converteste pe p dintr-un pointer la char intr-un pointer la o structura de sablon tnode, daca el apare intr-o expresie. Si atunci, o versiune a alocatorului talloc poate fi urmatoarea:

struct tnode *talloc() A char *alloc(); return (struct tnode *) alloc
(sizeof(struct tnode));
S
10.6. Cautare in tabele

O alta problema legata de definirea si utilizarea structurilor este cautarea in tabele. Cind se intilneste de exemplu, o linie de forma:
#define YES 1 simbolul YES si textul de substitutie 1 se memoreaza intr-o tabela. Mai tirziu, ori de cite ori textul YES va aparea in instructiuni, el se va inlocui cu constanta 1.
Crearea si gestionarea tabelelor de simboluri este o problema de baza in procesul de compilare. Exista doua rutine principale care gestioneaza simbolurile si textele lor de substitutie. Prima, install(s,t) inregistreaza simbolul s si textul de substitutie t intr-o tabela, s si t fiind siruri de caractere. A doua, lookup(s) cauta sirul s in tabela si returneaza fie un pointer la locul unde a fost gasit, fie NULL daca sirul s nu figureaza in tabel.
Algoritmul folosit pentru crearea si gestionarea tabelei de simboluri este o cautare pe baza de hashing. Fiecarui simbol i se calculeaza un cod hash astfel: se aduna codurile ASCII ale caracterelor simbolului si se ia restul provenit din impartirea numarului obtinut din adunare si dimensiunea tabelului. Astfel, fiecarui simbol i se asociaza un cod hash H care verifica relatia:
0<=H<0x100 (in hexazecimal)
Codul hash astfel obtinut va fi folosit apoi ca un indice intr-o tabela de pointeri. Un element al acestei tabele (masiv) indica inceputul unui lant de blocuri care descriu simboluri cu acelasi cod hash. Daca un element al tabelei este NULL inseamna ca nici un simbol nu are valoarea respectiva de hashing.
Un bloc dintr-un lant indicat de un element al tabelei este o structura care contine un pointer la simbol, un pointer la textul de substitutie si un pointer la urmatorul bloc din lant. Un pointer NULL la urmatorul bloc din lant indica sfirsitul lantului.
Sablonul unei structuri (nod) este urmatorul:

struct nlist A char *name; char *def; struct nlist *next;/ * urmatoarea intrare in lant */
S;

Tabelul de pointeri care indica inceputurile lantului de blocuri ce descriu simboluri de acelasi cod hash este:

#define HASHSIZE 0x100 static struct nlist *hashtabaHASHSIZEi;

Algoritmul de hashing pe care-l prezentam nu este cel mai bun posibil, dar are meritul de a fi extrem de simplu:

hash(char *s) A
/* formeaza valoarea hash pentru sirul s */ int hashval; for (hashval=0; *s!='\0';) hashval += *s++; return hashval % HASHSIZE;
S

Algoritmul de hashing produce un indice in masivul de pointeri hashtab. In procesul de cautare a unui simbol, daca el exista, el trebuie sa fie in lantul de blocuri care incepe la adresa continuta de elementul din hashtab cu indicele respectiv.
Cautarea in tabela de simboluri hashtab se realizeaza cu functia lookup. Daca simbolul cautat este prezent undeva in lant, functia returneaza un pointer la el; altfel returneaza NULL.

struct nlist *lookup(char *s) A
/* cauta sirul s in hashtab */ struct nlist *np; for (np=hashtabahash(s)i; np!=NULL; np=np->next) if (strcmp(s,np->name)==0) return np; /* s-a gasit s */ return NULL; /* nu s-a gasit s */
S

Rutina install foloseste functia lookup pentru a determina daca simbolul nou care trebuie introdus in lant este deja prezent sau nu. Daca mai exista o definitie anterioara pentru acest simbol, ea trebuie inlocuita cu definitia noua. Altfel, se creeaza o intrare noua pentru acest simbol, care se introduce la inceputul lantului. Functia install returneaza NULL, daca din anumite motive nu exista suficient spatiu pentru crearea unui bloc unu.

struct nlist *install(char *name, char
*def) A /* scrie (nume, def) in htab */ struct nlist *np, *lookup(); char *strsav(), *alloc(); int hashval; if ((np=lookup(name))==NULL) A /* nu s-a gasit */ np = (struct nlist*)alloc(sizeof(*np)); if (np==NULL) return NULL; /* nu exista spatiu */ if ((np->name=strsav(name))==NULL) return NULL; hashval = hash(np->name); np->next = hashtabahashvali; hashtabahashvali = np;
S else /* nodul exista deja */ free(np->def); /* elibereaza definitia veche */ if ((np->def=strsav(def))==NULL) return NULL; return np;
S

Deoarece apelurile la functiile alloc si free pot aparea in orice ordine si deoarece alinierea conteaza, versiunea simpla a functiei alloc, prezentata in capitolul 9 nu este adecvata aici. In biblioteca standard exista functii de alocare fara restrictii, care se apeleaza implicit sau explicit de catre utilizator dintr-un program scris in C pentru a obtine spatiul de memorie necesar. Deoarece si alte actiuni dintr-un program pot cere spatiu de memorie intr-o maniera asincrona, spatiul de memorie gestionat de functia alloc poate sa fie necontiguu. Astfel, spatiul liber de memorie este pastrat sub forma unui lant de blocuri libere, fiecare bloc continind o dimensiune, un pointer la urmatorul bloc si spatiul liber propriu-zis. Blocurile sint pastrate in ordinea crescatoare a adreselor iar, ultimul bloc, de adresa cea mai mare, indica primul bloc, prin pointerul lui la blocul urmator din lant, astfel incit lantul este circular.
Cind se lanseaza o cerere, se examineaza lista spatiului liber, pina se gaseste un bloc suficient de mare pentru cererea respectiva. Daca blocul are exact dimensiunea ceruta, el se elibereaza din lantul blocurilor libere si este returnat utilizatorului. Daca blocul este mai mare se descompune, astfel incit partea ceruta se transmite utilizatorului, iar partea ramasa se introduce inapoi in lista de spatiu liber. Daca nu se gaseste un bloc suficient de mare pentru cererea lansata se cauta un alt bloc de memorie.
Eliberarea unei zone de memorie prin intermediul rutinei free cauzeaza, de asemenea, o cautare in lista de spatiu liber, pentru a gasi locul corespunzator de inserare a blocului de memorie eliberat. Daca blocul de memorie eliberat este adiacent cu un bloc din lista de spatiu liber la orice parte a sa, el este alipit la acel bloc, creindu-se un bloc mai mare, astfel ca memoria sa nu devina prea fragmentata. Determinarea adiacentei este usurata de faptul ca lista de spatiu liber se pastreaza in ordinea crescatoare a adreselor de memorie.
Exemplul de utilizare a acestor functii initializeaza elementele masivului hashtab cu NULL. In continuare se asteapta de la tastatura introducerea unui nume si a unei definitii pentru acest nume. Daca numele introdus nu exista in lista hashtab atunci se afiseaza un mesaj corespunzator, altfel se afiseaza vechea definitie care este apoi inlocuita de noua definitie introdusa.

main() A char numa30i,defa30i; int i; struct nlist *np; for (i=0; i<HASHSIZE; i++) hashtabaii = NULL; do A getword(num); getword(def); if ((np=lookup(num))==NULL) printf("New name\n"); else printf("Old definition: %s\n", np->def); install(num,def);
S while (1);
S

10.7. Cimpuri

Un cimp se defineste ca fiind o multime de biti consecutivi dintr-un cuvint sau intreg. Adica din motive de economie a spatiului de memorie, este utila impachetarea unor obiecte intr-un singur cuvint masina. Un caz frecvent de acest tip este utilizarea unui set de flaguri, fiecare pe un bit, pentru tabela de simboluri a unui compilator.
Fiecare simbol dintr-un program are anumite informatii asociate lui, cum sint de exemplu, clasa de memorie, tipul, daca este sau nu cuvint cheie s.a.m.d. Cel mai compact mod de a codifica aceste informatii este folosirea unui set de flaguri, de cite un bit, intr-un singur intreg sau caracter.
Modul cel mai uzual pentru a face acest lucru este de a defini un set de masti, fiecare masca fiind corespunzatoare pozitiei bitului m interiorul caracterului sau cuvintului. De exemplu:

#define KEYWORD 01
#define EXTERNAL 02
#define STATIC 04

definesc mastile KEYWORD, EXTERNAL si STATIC care se refera la bitii 0, 1 si respectiv 2 din caracter sau cuvint. Atunci accesarea acestor biti se realizeaza cu ajutorul operatiilor de deplasare, mascare si complementare, descrisi intr-un capitol anterior. Numerele trebuie sa fie puteri ale lui 2.

Expresii de forma: flags | = EXTERNAL | STATIC; apar frecvent si ele seteaza bitii 1 si 2 din caracterul sau intregul flags (in exemplul nostru)

in timp ce expresia: flags &= (EXTERNAL | STATIC); selecteaza bitii 1 si 2 din flags.

Expresia: if (flags & (EXTERNAL | STATIC)) ... este adevarata cind cel putin unul din bitii 1 sau 2 din flags este unu.

Expresia: if (!(flags & (EXTERNAL | STATIC))) ... este adevarata cind bitii 1 si 2 din flags sint ambii zero.

Limbajul C ofera aceste expresii, ca o alternativa, pentru posibilitatea de a defini si de a accesa bitii dintr-un cuvint, in mod direct, folosind operatorii logici pe biti.

Sintaxa definitiei cimpului si a accesului la el se bazeaza pe structuri. De exemplu constructiile #define din exemplul de mai sus pot fi inlocuite prin definirea a trei cimpuri:

struct A unsigned is_keyword: 1; unsigned is_external:1; unsigned is_static: 1;
S flags;

Aceasta constructie defineste variabila flags care contine 3 cimpuri, fiecare de cite un bit. Numarul care urmeaza dupa ’:’ reprezinta lungimea cimpului in biti. Cimpurile sint declarate unsigned pentru a sublinia ca ele sint cantitati fara semn. Pentru a ne referi la un cimp individual din variabila flags folosim o notatie similara cu notatia folosita pentru membrii structurilor. flags.is_keyword flags.is_static
Cimpurile se comporta ca niste intregi mici fara semn si pot participa in expresii aritmetice ca orice alti intregi. Astfel, expresiile anterioare pot fi scrise mai natural sub forma urmatoare: flags.is_extern = flags.is_static = 1; pentru setarea bitilor 1 si 2 din variabila flags, flags.is_extern = flags.is_static = 0; pentru stergerea bitilor, iar:

if (flags.is_extern==0 && flags.is_static==0)

pentru testarea lor.
Un cimp nu trebuie sa depaseasca limitele unui cuvint. In caz contrar, cimpul se aliniaza la limita urmatorului cuvint. Cimpurile nu necesita sa fie denumite. Un cimp fara nume, descris numai prin caracterul ’:’ si lungimea lui in biti este folosit pentru a rezerva spatiu in vederea alinierii urmatorului cimp. Lungimea zero a unui cimp poate fi folosita pentru fortarea alinierii urmatorului cimp la limita unui nou cuvint, el fiind presupus a contine tot cimpuri si nu un membru obisnuit al structuri, deoarece in acest ultim caz, alinierea se face in mod automat. Nici un cimp nu poate fi mai lung decit un cuvint. Cimpurile se atribuie de la dreapta la stinga.
Cimpurile nu pot constitui masive, nu au adrese, astfel incit operatorul '&' nu se poate aplica asupra lor.

10.8. Reuniuni

O reuniune este o variabila care poate contine, la momente diferite, obiecte de diferite tipuri si dimensiuni; compilatorul este cel care tine evidenta dimensiunilor si aliniamentului.
Reuniunile ofera posibilitatea ca mai multe tipuri diferite de date sa fie tratate intr-o singura zona de memorie, fara a folosi in program vreo informatie dependenta de masina.
Sa reluam exemplul tabelei de simboluri a unui compilator, presupunind ca constantele pot fi de tip int, float sau siruri de caractere.
Valoarea unei constante particulare trebuie memorata intr-o variabila de tip corespunzator, cu toate ca este mai convenabil, pentru gestiunea tabelei de simboluri, ca valoarea sa fie memorata in aceeasi zona de memorie, indiferent de tipul ei si sa ocupe aceeasi cantitate de memorie. Acesta este scopul unei reuniuni: de a furniza o singura variabila care sa poata contine oricare dintre valorile unor tipuri de date. Ca si in cazul cimpurilor, sintaxa definitiei si accesului la o reuniune se bazeaza pe structuri. Fie definitia:

union u_tag. A int ival; float fval; char *pval;
S uval;

Variabila uval va fi suficient de mare ca sa poata pastra pe cea mai mare dintre cele trei tipuri de componente. Oricare dintre tipurile de mai sus poate fi atribuit variabilei uval si apoi folosit in expresii in mod corespunzator, adica tipul in uval este tipul ultim atribuit. Utilizatorul este cel care tine evidenta tipului curent memorat intr-o reuniune.
Sintactic, membrii unei reuniuni sint accesibili printr-o constructie de forma: nume-reuniune. membru sau pointer-la-reuniune->membru
Daca variabila utype este utilizata pentru a tine evidenta tipului curent memorat in uval, atunci fie urmatorul cod:

if (utype==INT) printf ("%d\n",uval.ival); else if (utype== FLOAT) printf("%f\n",uval.fval); else if (utype==STRING) printf("%s\n",uval.pval); else printf("tip incorect %d in utype\n", utype);

Reuniunile pot aparea in structuri si masive si invers. Sintaxa pentru accesarea unui membru al unei reuniuni, dintr-o structura, sau invers este identica cu cea pentru structurile imbricate. Pe exemplu, in masivul de structuri symtabaNSYMi definit de:

struct A char * name; int flags; int utype; union A int ival; float fval; char *pval;
S uval;
S symtabaNSYMi;

variabila ival se refera prin: symtabaii.uval.ival iar primul caracter al sirului pointat de pval prin:
*symtabaii.uval.pval
De fapt, o reuniune este o structura in care toti membrii au deplasamentul zero, structura fiind suficient de mare pentru a putea pastra pe cel mai mare membru. Alinierea este corespunzatoare pentru toate tipurile reuniunii. Ca si la structuri, singurele operatii permise cu reuniuni sint accesul la un membru al reuniunii si considerarea adresei ei.
Reuniunile nu pot fi atribuite, transmise la functii sau returnate de catre acestea. Pointerii la reuniuni pot fi folositi in mod similar cu pointerii la structuri.

10.9. Declaratii de structuri, reuniuni si cimpuri

Deoarece specificatorii de structuri, reuniuni si cimpuri au aceeasi forma vom prezenta sintaxa lor generala in acest paragraf.

Specificator-structura-sau-reuniune: struct-sau-union A lista-declaratiilor S struct-sau-union identificator A lista-declaratiilor S struct-sau-union identificator
Struct-sau-union: struct union

Lista-declaratiilor este o secventa de declaratii pentru membrii structurii sau reuniunii.

Lista-declaratiilor: declaratie-structura declaratie-structura, lista-declaratiilor
Declaratie-structura: specificator-tip, lista-declarator;
Lista-declarator: declarator-structura declarator-structura, lista-declarator

In mod obisnuit, un declarator-structura este chiar un declarator pentru un membru al structurii sau reuniunii. Un membru al structurii poate fi constituit dintr-un numar specificat de biti, caz in care avem de-a face cu un cimp. Lungimea lui se separa de nume prin caracterul ’:’ Atunci:

Declarator-structura: declarator declarator : expresie-constanta
: expresie-constanta

Intr-o structura fiecare membru care nu este un cimp incepe la o adresa corespunzatoare tipului sau. Astfel intr-o structura pot exista zone fara nume neutilizate, rezultate din motive de aliniere.
Limbajul C nu introduce restrictii privind tipurile obiectelor care pot fi declarate cimpuri.
Un specificator-structura-sau-reuniune de forma a doua declara un identificator ca fiind eticheta (marcajul) structurii sau reuniunii. Atunci o declaratie ulterioara poate folosi forma a treia a unui specificator-structura-sau-reuniune.
Etichetele de structuri permit definirea structurilor auto-referite; de asemenea permit ca partea de declaratie a corpului structurii sa fie data o singura data si folosita de mai multe ori. Este interzisa declararea recursiva a unei structuri sau reuniuni, dar o structura sau o reuniune poate contine un pointer la ea.
Doua structuri pot partaja o secventa initiala comuna de membri; adica acelasi membru poate aparea in doua structuri diferite daca el are acelasi tip in ambele structuri si daca toti membri precedenti lui sint identici in cele doua structuri.

10.10. Typedef

Limbajul C ofera o facilitate numita typedef pentru a crea noi nume de tipuri de date. Specificatorul de tip typedef-nume are sintaxa: typedef-nume: declarator

Intr-o declaratie implicind typedef fiecare identificator care apare ca parte a unui declarator devine sintactic echivalent cu cuvintul cheie rezervat pentru tipul asociat cu identificatorul. De exemplu, declaratia: typedef int LENGTH;
il face pe LENGTH sinonim cu int. „Tipul” LENGTH poate fi folosit ulterior in declaratii in acelasi mod ca si tipul int.
LENGTH len, maxlen;
LENGTH *lengthai;
In mod similar, declaratia: typedef char *STRING;
il face pe STRING sinonim cu char*, adica pointer la caracter, care apoi poate fi utilizat in declaratii de tipul:
STRING p, lineptraLINESi, alloc();
Se observa ca tipul care se declara prin typedef apare pe pozitia numelui de variabila nu imediat dupa cuvintul rezervat typedef. Sintactic typedef este sinonim cu clasele de memorie extern, static etc, dar nu rezerva memorie pentru variabilele respective.
Ca un exemplu mai complicat sa reluam declaratia unui nod al unui arbore, de data aceasta folosind typedef pentru a crea un nou nume pentru un tip structura (vezi sectiunea 10.5).

typedef struct tnode A char *word; /* pointer la text */ int count; /* numar aparitii */ struct tnode *left; /* descendent sting */ struct tnode *right; /* descendent drept */
S TREENODE, *TREEPTR;

Aceasta declaratie creeaza doua nume noi de tipuri, numite TREENODE, care este o structura si TREEPTR, care este un pointer la o structura. Atunci rutina talloc poate fi scrisa sub forma:

TREEPTR talloc() A char *alloc(); return (TREEPTR)alloc(sizeof(TREENODE)));
S

Trebuie subliniat faptul ca declaratia typedef nu creeaza noi tipuri in nici un caz; ea adauga doar sinonime pentru anumite tipuri de date, deja existente. Variabilele declarate in acest fel au exact aceleasi proprietati ca si cele declarate explicit. De fapt, typedef se aseamana cu #define, cu exceptia faptului ca in timp ce #define este tratat de preprocesor, typedef este tratat de catre compilator. De exemplu: typedef int(*PFI)(); creeaza numele PFI pentru „pointer la o functie care returneaza un intreg”, tip care poate fi folosit ulterior intr-un context de tipul:
PFI strcmp, numcmp, swap;
in programul de sortare din capitolul 9.
Exista doua motive principale care impun folosirea declaratiilor typedef. Primul este legat de problemele de portabilitate. Cind se folosesc declaratii typedef pentru tipuri de date care sint dependente de masina, atunci pentru o compilare pe un alt sistem de calcul este necesara modificarea doar a acestor declaratii nu si a datelor din program.
Al doilea consta in faptul ca prin crearea de noi nume de tipuri se ofera posibilitatea folosirii unor nume mai sugestive in program, deci o mai rapida intelegere a programului.