Programarea Calculatoarelor: Laborator 12

Structuri și câmpuri pe biți

Pe lăngă cămpuri obișnuite, structurile pot avea și câmpuri pe biți: valori de tip întreg reprezentate pe un număr specificat de biți. În acest fel putem reprezenta mai eficient valori mici, care nu necesită numărul de biți pe care se reprezintă obișnuit un întreg (16, 32 sau chiar 64). Mai multe câmpuri de acest tip pot ocupa biți succesivi din octeți succesivi din memorie, rezultând într-o reprezentare mai compactă decât dacă s-ar folosi un număr întreg de octeți pentru fiecare câmp. În același timp, valorile pot fi accesate mai natural și mai simplu (cu sintaxa variabilă.câmp) decât cu măști și operatori pe biți.

Limbajul C nu precizează detalii despre ordinea în care sunt dispuși biții în astfel de structuri; acesta poate fi dependent de arhitectură și compilator, deci înainte de a ne baza pe o anumită dispunere trebuie să verificăm cu exemple.

Definim o astfel de structură pentru a reprezenta un moment de timp format din dată și oră. De exemplu, secundele și minutele iau valori între 0 și 59, deci se pot reprezenta pe 6 biți (pe care încap valori până la 26-1, deci 63). Zilele (de la 1 la 31) se pot reprezenta pe 5 biți, la fel și orele, iar lunile pe 4 biți. Încercând să folosim doar 32 de biți în total (la fel ca și un tip întreg) ne mai rămân 6 biți pentru an. Alegem să reprezentâm anii începând de la 1980 (pe care îl reprezentăm ca 0), și putem astfel ajunge până la 1980 + 63 = 2043. Putem scrie structura în felul următor:

#define SECBITS	6
#define MINBITS 6

typedef struct date {
  int sec : SECBITS;
  int min : MINBITS;
  int hr : 5;
  int day : 5;
  int mo : 4;
  int yr : 6;
} date_t;
Numărul de biți e precizat după : pentru fiecare câmp; pentru primele câmpuri am folosit macro-uri (constante simbolice), care ne vor ajuta să scriem mai flexibil și ușor de înțeles codul care urmează.

Putem folosi o variabilă de acest tip ca și orice structură obișnuită și putem verifica câți octeți ocupă o astfel de structură pe sistemul nostru (un răspuns posibil: 4).

  date_t t;
  printf("sizeof(struct date) = %u\n", sizeof(date_t));
  t.yr = 2008 - 1980; t.mo = 5; t.day = 24;
  t.hr = 15; t.min = 47; t.sec = 33;
Pentru a verifica cum sunt reprezentate datele în memorie declarăm o variabilă întreagă de aceeași dimensiune, îi atribuim valoarea aflată la adresa variabilei dată (deci octeții de memorie care formează data, priviți ca și întreg) și îi tipărim câmpurile folosind operatori pe biți. Pe o arhitectură Intel x86 / gcc / Linux, câmpurile sunt reprezentate pornind de la bitul cel mai puțin semnificativ. Pentru a extrage câmpurile, deplasăm întregul d până când câmpul dorit ajunge pe biții cei mai puțin semnificativi, și apoi facem un ȘI cu o mască cu biții respectivi pe 1, și ceilalți pe 0.
#define SECOFF	0
#define MINOFF	SECBITS		// de la ce pozitie incep bitii de minut
#define MASK(bits)	~(~0u << bits)	// 1 pe bits pozitii 

  uint32_t d = *(uint32_t *)&t;	// privim valoarea de la &t ca si intreg
  printf("%u minute %u secunde\n", d >> MINOFF & MASK(MINBITS),
	 d & MASK(SECBITS));

Programul complet se găsește aici. Extindeți programul tipărind și alte câmpuri (ora, ziua, etc.) din structură. Scrieți apoi o funcție care returnează o structură reprezentând data și ora aflată la un număr dat de secunde după începutul anului 1980 (de exemplu: un miliard de secunde).

Scrierea de programe modulare

Până acum am scris de regulă programe formate dintr-un singur fișier C. În exemplele inițiale cu grafică am compilat însă programe formate din mai multe fișiere: funcțiile grafice erau deja date (definite) în alt fișier și trebuiau declarate În fișierul program scris ca exercițiu. Ilustrând cu un exemplu extrem de simplu:

Scriem o funcție care face suma a două numere, în fișierul suma.c:

// fisierul suma.c
int suma(int a, int b)
{
  return a + b;
}
Acest fișier poate fi compilat (dar nu rulat, pentru că nu are main), și se obtine un fișier obiect cu codul obiect (în limbaj mașină) al funcției:
gcc -c suma.c
Opțiunea -c spune compilatorului să compileze doar în format obiect, fără să încerce crearea unui fișier executabil. Va rezulta fișierul obiect suma.o

Pentru a folosi funcția, putem scrie programul simplu.c astfel, declarănd funcția suma pentru ca ea să fie recunoscută de compilator în momentul apelului:

// fisierul simplu.c

// declaratia functiei
int suma(int a, int b);

int main(void)
{
  printf("%d\n", suma(5, 3));
  return 0;
}
Acest fișier C putem de asemenea să-l compilăm în format obiect:
gcc -c simplu.c
rezultând fișierul obiect simplu.o. Putem apoi combina (engl. link, rom. editare de legături) cele două fișiere executabile, cu comanda:
gcc -o simplu suma.o simplu.o
În acest fel, am separat implementarea funcției suma de programul care o folosește. Dacă modificăm funcția (păstrând însă același tip pentru parametri și rezultat) nu trebuie decât să edităm și să recompilăm fișierul suma, și să refacem programul executabil. Invers, putem modifica programul nostru fără să modificăm sau să recompilăm funcția.

În loc să scriem direct în program declarația funcției suma, am putea să creem un fișier antet (header) care să conțină această declarație:

// fisierul suma.h
int suma(int a, int b);
Putem rescrie atunci programul nostru:
// fisierul simplu.c

#include "suma.h"

int main(void)
{
  printf("%d\n", suma(5, 3));
  return 0;
}
Efectul este de a include conținutul fișierului suma.h în programul nostru, adică exact declarația funcției. Sintaxa cu ghilimele "suma.h" e recomandată pentru fișierele scrise de noi (spre deosebire de cele standard), iar multe compilatoare caută fișierul întâi în catalogul curent.

Crearea unui fișier antet e utilă când acesta conține mai multe declarații, astfel programatorul care le folosește nu trebuie să repete scrierea tuturor și se elimină și potențialele greșeli.

Structuri de date de tip asociere/dicționar (hashmap/hashtable)

O situație foarte des întâlnită este cea în care trebuie să implementăm o funcție (asociere) de la un tip de date cu valori în alt tip de date. De exemplu, să asociem unei entități identificate printr-un nume (un șir de caractere) o valoare numerică sau de alt tip (nota sau bursa unui student, adresa sau CNP-ul unei persoane, explicația din dicționar pentru un cuvânt, etc). Pentru funcțiile pe intervale continue de întregi putem folosi un tablou care ne asociază la un indice întreg un element de tipul dorit, dar nu și dacă obiectul despre care dorim informația are un tip arbitrar.

Am putea implementa o listă de structuri cu două câmpuri (obiectul și informația dorită), dar căutarea obiectului dorit în listă s-ar face foarte lent. Din acest motiv, asocierea se implementează în doi pași: prin aplicarea unei funcții hash se calculează o valoare întreagă corespunzătoare obiectului dat, care e folosită ca indice într-un tablou. La acel indice în tablou se păstrează o structură cu obiectul și valoarea asociată. Pentru că prin aplicarea funcției mai multe obiecte pot căpăta același indice, se păstrează o >listă cu toate perechile (obiect, valoare) pentru același indice hash. Dacă tabelul e suficient de mare și funcția hash bine aleasă pentru a uniformiza distribuția, listele pentru fiecare indice sunt scurte și obiectul e găsit ușor.

Fișierul hashmap.c implementează un astfel de dicționar care asociază unui șir o valoare numerică a cărei semnificație poate fi aleasă în funcție de problema de rezolvat. El definește o structură cu trei cămpuri: șirul, valoarea asociată, și o adresă de legătură pentru următoarea structură care are aceeași valoare de indice în tabel.

struct ent {		// o intrare in tabela de dispersie
  char *key;		// sirul (cheia de cautare)
  int val;		// informatia despre sir
  struct ent *next;	// urmatoarea intrare
};
Fișierul hashmap.h declară funcțiile pe care hashmap.c le implementează pentru acest tip de date. De asemenea, el definește tipurile entry_t ca pointer la tipul structură amintit anterior, și hash_t pentru tabela de dispersie (hash table): adresa unui tablou de adrese de tipul entry_t. Dacă un element de tablou (adresă) e nul, nu există obiecte asociate cu acel indice; altfel, adresa indică prima din structurile din listă, care e legată la următoarea, până la atingerea unui pointer NULL.
typedef struct ent *entry_t;
typedef entry_t *hash_t;
Funcția hash_create creează un astfel de tablou de adrese, de dimensiune fixă, și îi returnează adresa. Funcția hash_free îl eliberează, parcurgându-l și eliberând fiecare structură din tabel, și în final spațiul de memorie ocupat de tabloul propriu-zis de adrese.

Funcția hash_get returnează valoarea (întreagă) asociată unui obiect (de tip șir). În primul rând, ea apelează funcția hash care calculează o valoare întreagă din șirul dat ("amestecând" cât mai bine valorile tuturor caracterelor componente) care determină la ce indice ar putea fi găsit obiectul. Apoi șirul e căutat (prin comparare cu strcmp) în lista de la acel indice, și se returnează valoarea asociată sau o valoare distinctivă dacă nu a fost găsit. Similar există funcții care inserează o nouă pereche (obiect, valoare) în tabel, schimbă valoarea asociată unui obiect, sau o modifică pe cea veche după o funcție dată ca parametru

O facilitate foarte utilă e de a putea enumera toate obiectele memorate în tabel, și a apela o funcție pentru fiecare din ele. Acest lucru e făcut de funcția hash_iter.

Un exemplu simplu de folosire a unei astfel de structuri e dat în programul hashtest.c. Acesta introduce în structură câteva perechi de tipul (student, nota) și afișează apoi toate perechile care satisfac o anumită condiție.

Sugestii de programe:


Marius Minea
Last modified: Sat May 24 17:38:25 EET 2008