Programarea Calculatoarelor: Laborator 12

Structuri şi câmpuri 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 2⁶-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;

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;

#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

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;
}

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;
}

Î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);

// fisierul simplu.c

#include "suma.h"

int main(void)
{
  printf("%d\n", suma(5, 3));
  return 0;
}

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)

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
};

typedef struct ent *entry_t;
typedef entry_t *hash_t;